\(\alpha\)-vertex separator is NP-hard even for 3-regular graphs

DOI10.1007/BF02257778zbMath0746.68042MaRDI QIDQ1179551

Rudolf Müller, Dorothea Wagner

Publication date: 26 June 1992

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

vertex separationPLA-folding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partitions of sets (05A18) Graph theory (05C99)

Related Items (2)

PLA folding in special graph classes ⋮ Balanced line separators of unit disk graphs

Cites Work

• Some simplified NP-complete graph problems
• A Separator Theorem for Planar Graphs
• The NP-completeness column: An ongoing guide
• Unnamed Item
• Unnamed Item

This page was built for publication: \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs