TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1989

COGA 5-Wheel


zur Navigation

Preprints 1989

Graph Separation is $N\!\!P$-hard even for Graphs with Bounded Degree
Zitatschlüssel Report-215-1989
Autor Dorothea Wagner and Frank Wagner
Jahr 1989
Nummer 215
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung One of the basic problems in VLSI-layout is the construction of a minimal decomposition of a graph, i.e. a partition or cut of the vertex-set into two pieces of not too different size which cuts the least possible number of edges. Not too different means that the size of each of the parts is at least a constant fraction of the total number of the graph vertices. We show that (the decision version of) this problem is $\cal NP$-hard. The result holds even if the graphs to be separated have maximal degree four, a typical restriction in the theory of VLSI layout.
Typ der Publikation Preprint
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe