An O(qn) algorithm to q-color a proper family of circular arcs (Q1060020): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Q686171 / rank | |||
Property / author | |||
Property / author: Alan C. Tucker / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a routing problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Complexity of Coloring Circular Arcs and Chords / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matrix characterizations of circular-arc graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Structure theorems for some circular-arc graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4173373 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Efficient Test for Circular-Arc Graphs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(85)90052-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2074047667 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:39, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An O(qn) algorithm to q-color a proper family of circular arcs |
scientific article |
Statements
An O(qn) algorithm to q-color a proper family of circular arcs (English)
0 references
1985
0 references
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.
0 references
minimal arc coloring
0 references
proper arc coloring
0 references
shortest path problem
0 references
shortest-path network
0 references