An approximation algorithm for circular arc colouring

DOI10.1007/S00453-001-0023-9MaRDI QIDQ5945920zbMATH OpenOpenAlexFDO

Authors V. Kumar

Publication date 14 October 2001

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-001-0023-9

zbMATH Keywords

colouringrandomized rounding

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 1182769
• Perfect circular arc coloring
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• An O(qn) algorithm to q-color a proper family of circular arcs
• STACS 2004

Cited in

(9)

• 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 constrained bipartite edge coloring
• Perfect circular arc coloring
• An Approximation Algorithm for the Smallest Color-Spanning Circle Problem
• scientific article; zbMATH DE number 1182769 (Why is no real title available?)
• Line system design and a generalized coloring problem
• An approximation result for a periodic allocation problem
• On the complexity of bandwidth allocation in radio networks

This page was built for publication: An approximation algorithm for circular arc colouring

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