Circular-arc graph coloring: On chords and circuits in the meeting graph

DOI10.1016/S0377-2217(01)00058-3zbMath1008.90067OpenAlexW1998629568MaRDI QIDQ5953338

Christine Eisenbeis, Elena A. Stöhr, Sylvain Lelait, Dominique de Werra

Publication date: 23 January 2002

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(01)00058-3

zbMATH Keywords

heuristicsgraph coloringgraph theorygraph decomposition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Coloring of graphs and hypergraphs (05C15)

Related Items

On interval and circular-arc covering problems

Uses Software

• NAS Parallel Benchmarks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maintaining knowledge about temporal intervals
• Approximate triclique coloring for register allocation
• An O(qn) algorithm to q-color a proper family of circular arcs
• Linear time algorithms on circular-arc graphs
• New clique and independent set algorithms for circle graphs
• On a graph-theoretical model for cyclic register allocation
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Efficient algorithms for interval graphs and circular-arc graphs
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Coloring a Family of Circular Arcs