Approximating the domatic number

DOI10.1145/335305.335321MaRDI QIDQ3191980zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Guy Kortsarz, Uriel Feige

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335321

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Recommendations

• Approximating theDomatic Number
• Approximations of the domination number of a graph
• Approximation hardness of dominating set problems in bounded degree graphs
• Algorithms – ESA 2004
• An improved exact algorithm for the domatic number problem

Cited in

(12)

• Approximation in (poly-) logarithmic space
• Maximum agreement and compatible supertrees
• Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
• New approximation results for resource replication problems
• Domatic partitions and the Lovász local lemma
• Disjoint bases in a polymatroid
• scientific article; zbMATH DE number 1954391 (Why is no real title available?)
• Approximations of the domination number of a graph
• Approximating theDomatic Number
• Algorithms with large domination ratio
• An improved exact algorithm for the domatic number problem
• Finding domatic partitions in infinite graphs

This page was built for publication: Approximating the domatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191980)