Publication Type
Journal Article
Version
publishedVersion
Publication Date
1997
Abstract
We present practical algorithms for constructing partitions of graphs into a fixed number of vertex-disjoint subgraphs that satisfy particular degree constraints. We use this in particular to find k-cuts of graphs of maximum degree ∆ that cut at least a k - 1/k (1 + 1/2∆+k-1 ) fraction of the edges, improving previous bounds known. The partitions also apply to constraint networks, for which we give a tight analysis of natural local search heuristics for the maximum constraint satisfaction problem. These partitions also imply efficient approximations for several problems on weighted bounded-degree graphs. In particular, we improve the best performance ratio for the weighted independent set problem to 3/∆+2 , and obtain an efficient algorithm for coloring 3-colorable graphs with at most 3∆+2/4 colors.
Discipline
Numerical Analysis and Scientific Computing
Publication
Journal of Graph Algorithms and Applications
Volume
1
Issue
3
First Page
1
Last Page
13
ISSN
1526-1719
Identifier
10.7155/jgaa.00003
Citation
Halldorsson, Magnus M. and Lau, Hoong Chuin.
Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring. (1997). Journal of Graph Algorithms and Applications. 1, (3), 1-13.
Available at: https://ink.library.smu.edu.sg/sis_research/173
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.7155/jgaa.00003