\(\alpha\)-vertex separator is NP-hard even for 3-regular graphs (Q1179551)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs |
scientific article |
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
