direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1990

α-Vertex-Separation is $N\!\!P$-hard even for 3-regular Graphs
Zitatschlüssel Report-225-1989
Autor Rudolf Müller and Dorothea Wagner
Seiten 343-353
Jahr 1989
Journal COMPUTING, 1990
Jahrgang 46
Nummer 225
Notiz extended abstract in Methods of Operations Research 62 (1990)\/, pp. 291-293)
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Download Bibtex Eintrag