TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1993

Between Min Cut and Graph Bisection
Zitatschlüssel Report-307-1991
Autor Dorothea Wagner and Frank Wagner
Buchtitel Proc. of 18th Symposium on Mathematical Foundations of Computer Science (MFCS'93), 1993
Seiten 744-750
Jahr 1991
Nummer 307
Herausgeber A. M. Borzyszkowski, S. Sokolowski
Serie Lecture Notes in Computer Science 711
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We investigate a class of graph partitioning problems whose two extreme representatives are the well-known Min Cut and Graph Bisection problems. The former is known to be efficiently solvable by flow techniques, the latter to be $\cal NP$-complete. The results presented in this paper are: A monotony result of the type ``The more balanced the partition we look for has to be, the harder the problem
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe