Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs

DOI10.1016/0166-218X(94)00118-WzbMath0847.68084OpenAlexW2091112956MaRDI QIDQ1917245

S. S. Ravi, Harry B. III Hunt, Madhav V. Marathe

Publication date: 5 August 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00118-w

zbMATH Keywords

interval graphscircular arc graphsNP-hard optimization problems

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Optimal on-line coloring of circular arc graphs ⋮ Efficient parallel recognition of some circular arc graphs. II

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating sets and domatic number of circular arc graphs
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• A polynomial time approximation algorithm for dynamic storage allocation
• Linear algorithm for domatic number problem on interval graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Efficient algorithms for interval graphs and circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords
• Coloring a Family of Circular Arcs
• Towards a theory of domination in graphs
• The file distribution problem for processor networks

This page was built for publication: Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs