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,...
محفوظ في:
| المؤلفون الرئيسيون: | , |
|---|---|
| التنسيق: | 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 |