An \(0(n^{1.5})\) algorithm to color proper circular arcs

DOI10.1016/0166-218X(89)90011-5zbMath0682.68062OpenAlexW2053308050MaRDI QIDQ1824396

Yanyan Li

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0166-218x(89)90011-5

zbMATH Keywords

NP-hardcoloringshortest path problembinary searchproper circular arcsTeng and Tucker's algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

Periodic assignment and graph colouring ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Unnamed Item ⋮ Asymptotics of the chromatic number for quasi-line graphs ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Circular-arc graph coloring: On chords and circuits in the meeting graph ⋮ Edge-coloring of 3-uniform hypergraphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ ⋮ Perfect circular arc coloring

Cites Work

• Unnamed Item
• An O(qn) algorithm to q-color a proper family of circular arcs
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords

This page was built for publication: An \(0(n^{1.5})\) algorithm to color proper circular arcs