TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1990

COGA 5-Wheel

Page Content

to Navigation

Preprints 1990

α-Vertex-Separation is $N\!\!P$-hard even for 3-regular Graphs
Citation key Report-225-1989
Author Rudolf Müller and Dorothea Wagner
Pages 343-353
Year 1989
Journal COMPUTING, 1990
Volume 46
Number 225
Note extended abstract in Methods of Operations Research 62 (1990)\/, pp. 291-293)
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Two discrete optimization problems arising in VLSI are to reduce the area of a programmable logic array (PLA) and to separate graphs uniformly. We show that a commonly used area reduction technique called blockfolding is equivalent to separating graphs by vertex delition. The later problem is shown to be NP-complete even for $3$-regular-graphs.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe