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

✍ Scribed by Austin Teng; Alan Tucker

• Publisher: Elsevier Science
• Year: 1985
• Tongue: English
• Weight: 683 KB
• Volume: 55
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(85)90052-4

✦ Synopsis

A family of arcs on a circle is proper if no arc is properly contained within another. While general minimal arc coloring is NP-complete, Orlin et al. recently obtained on O(n') algorithm for q-coloring a proper family of arcs by modeling proper arc coloring as a shortest path problem in an associated network (with negative edges). This paper simplifies Orlin's shortestpath network to obtain an O(qn) time algorithm.