Publication Type

Journal Article

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

Research Areas

Intelligent Systems and Decision Analytics

Publication

Journal of Graph Algorithms and Applications

Volume

1

Issue

3

First Page

1

Last Page

13

ISSN

1526-1719

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5060

Share

COinS