An O(qn) algorithm to q-color a proper family of circular arcs

DOI10.1016/0012-365X(85)90052-4MaRDI QIDQ1060020zbMATH OpenOpenAlexFDO

Authors Austin Teng, Alan C. Tucker

Publication date 1985

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(85)90052-4

zbMATH Keywords

shortest path problemminimal arc coloringproper arc coloringshortest-path network

Mathematics Subject Classification ID

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

Recommendations

• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Perfect circular arc coloring
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• scientific article; zbMATH DE number 4051024
• An approximation algorithm for circular arc colouring

Cites work

• scientific article; zbMATH DE number 3608050 (Why is no real title available?)
• An O(n^2 ) Algorithm for Coloring Proper Circular Arc Graphs
• An Efficient Test for Circular-Arc Graphs
• Matrix characterizations of circular-arc graphs
• On a routing problem
• Structure theorems for some circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(13)

• An approximation algorithm for circular arc colouring
• Polyhedral sets and integer rounding
• Perfect circular arc coloring
• Scheduling electric vehicle regular charging tasks: a review of deterministic models
• Edge-coloring of 3-uniform hypergraphs
• Circular-arc graph coloring: On chords and circuits in the meeting graph
• Periodic assignment and graph colouring
• Precoloring extension on unit interval graphs
• Interval graphs and related topics
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Algorithmic aspects of intersection graphs and representation hypergraphs
• Intersection graphs of proper subtrees of unicyclic graphs
• Bounding χ in terms of ω and Δ for quasi-line graphs

This page was built for publication: An O(qn) algorithm to q-color a proper family of circular arcs

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