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

DOI10.1016/S0377-2217(01)00058-3MaRDI QIDQ5953338zbMATH OpenOpenAlexFDO

Authors Dominique De Werra, Christine Eisenbeis, Sylvain Lelait, Elena Stöhr

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 theorygraph coloringgraph 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)

Recommendations

• On a graph-theoretical model for cyclic register allocation
• On \(k\)-coloring of weighted circular-arc graphs
• Perfect circular arc coloring
• Programming Languages and Systems
• An \(0(n^{1.5})\) algorithm to color proper circular arcs

Cites work

• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1303600 (Why is no real title available?)
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• An O(qn) algorithm to q-color a proper family of circular arcs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Approximate triclique coloring for register allocation
• Coloring a Family of Circular Arcs
• Efficient algorithms for interval graphs and circular-arc graphs
• Linear time algorithms on circular-arc graphs
• Maintaining knowledge about temporal intervals
• New clique and independent set algorithms for circle graphs
• On a graph-theoretical model for cyclic register allocation
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(2)

• On \(k\)-coloring of weighted circular-arc graphs
• On interval and circular-arc covering problems

Describes a project that uses

Uses Software

• NAS Parallel Benchmarks

This page was built for publication: Circular-arc graph coloring: On chords and circuits in the meeting graph

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