Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring

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,...

全面介紹

Saved in:
書目詳細資料
Main Authors: Halldorsson, Magnus M., Lau, Hoong Chuin
格式: text
語言:English
出版: Institutional Knowledge at Singapore Management University 1997
主題:
在線閱讀:https://ink.library.smu.edu.sg/sis_research/173
https://ink.library.smu.edu.sg/context/sis_research/article/1172/viewcontent/LauC1997LowDegree_Graph.pdf
標簽: 添加標簽
沒有標簽, 成為第一個標記此記錄!
機構: Singapore Management University
語言: English
實物特徵
總結: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.