Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring

DOI10.7155/jgaa.00003zbMath0891.05061OpenAlexW2163269124MaRDI QIDQ4381058

Magnús M. Halldórsson, Hoong Chuin Lau

Publication date: 1 April 1998

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/47893

zbMATH Keywords

partitions algorithms bounds coloring performance ratio independent set problem degree constraints

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Inductive graph invariants and approximation algorithms ⋮ Planarization and fragmentability of some classes of graphs ⋮ Local approximations for maximum partial subgraph problem. ⋮ On the max min vertex cover problem ⋮ Pairwise-Interaction Games ⋮ New results on \(k\)-independence of graphs ⋮ On monochromatic component size for improper colourings ⋮ Algorithm for optimal winner determination in combinatorial auctions ⋮ Independent sets in bounded-degree hypergraphs ⋮ Approximation algorithms for the weighted independent set problem in sparse graphs ⋮ A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs

This page was built for publication: Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring