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

• المؤلفون الرئيسيون: Halldorsson, Magnus M., Lau, Hoong Chuin
• التنسيق: text
• اللغة: English
• منشور في: Institutional Knowledge at Singapore Management University 1997
• الموضوعات: Numerical Analysis and Scientific Computing
• الوصول للمادة أونلاين: 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

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