Approximating the domatic number

DOI10.1145/335305.335321zbMath1296.05150OpenAlexW2045801654MaRDI QIDQ3191980

Magnús M. Halldórsson, Guy Kortsarz

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)

Related Items (6)

New approximation results for resource replication problems ⋮ An improved exact algorithm for the domatic number problem ⋮ Finding domatic partitions in infinite graphs ⋮ Maximum agreement and compatible supertrees ⋮ Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms ⋮ Disjoint bases in a polymatroid

This page was built for publication: Approximating the domatic number