An O(qn) algorithm to q-color a proper family of circular arcs
type: Item
instance of: scholarly article
title: An O(qn) algorithm to q-color a proper family of circular arcs
zbMATH Open document ID: 0567.68043
DOI: 10.1016/0012-365X(85)90052-4
author: Austin Teng
author: Alan C. Tucker
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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, \textit{J. B. Orlin}, \textit{M. A. Bonuccelli} and \textit{D. P. Bovel} [SIAM J. Algebraic Discrete Methods 2, 88-93 (1981; Zbl 0496.68047)] obtained on \(O(n^ 2)\) 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 shortest-path network to obtain an O(qn) time algorithm.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3905862
zbMATH Keywords: minimal arc coloring
zbMATH Keywords: proper arc coloring
zbMATH Keywords: shortest path problem
zbMATH Keywords: shortest-path network
MaRDI profile type: Publication
cites work: On a routing problem
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
cites work: Matrix characterizations of circular-arc graphs
cites work: Structure theorems for some circular-arc graphs
cites work: Q4173373
cites work: An Efficient Test for Circular-Arc Graphs
full work available at URL: 0012-365x(85)90052-4
OpenAlex ID: W2074047667
description: scientific article; zbMATH DE number 3905862