Title
Between Min Cut and Graph Bisection
Authors
-
Publication
Lecture Notes in Computer Science 711, Proc. of 18th Symposium on Mathematical Foundations
of Computer Science (MFCS'93), ed. A. M. Borzyszkowski, S. Sokolowski, 1993, pp. 744-750
Source
-
Classification
-
not available
Keywords
-
not available
-
-
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{"}, and a complexity
result clarifying the status of a large part of
intermediate problems in the class. Thus we show the
existence and partly localize an "efficiency border{"}
between the two extremes.
