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

graph coloringgraph decompositiongraph theoryheuristics

Mathematics Subject Classification ID

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

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

• An O(n^2 ) Algorithm for Coloring Proper Circular Arc Graphs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• An O(qn) algorithm to q-color a proper family of circular arcs
• Approximate triclique coloring for register allocation
• Coloring a Family of Circular Arcs
• Efficient algorithms for interval graphs and circular-arc graphs
• 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?)
• 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

(3)

• On a graph-theoretical model for cyclic register allocation
• 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)