\(\alpha\)-vertex separator is NP-hard even for 3-regular graphs (Q1179551)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs |
scientific article; zbMATH DE number 24907
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs |
scientific article; zbMATH DE number 24907 |
Statements
\(\alpha\)-vertex separator is NP-hard even for 3-regular graphs (English)
0 references
26 June 1992
0 references
The authors show that an in VLSI used area reduction technique called blockfolding is equivalent to separating graphs by vertex deletion. The later problem is shown to be \(NP\)-hard even for 3-regular graphs. The proof of this complexity result uses a transformation technique to the \(\alpha\)-edge separator.
0 references
vertex separation
0 references
PLA-folding
0 references
