An O(qn) algorithm to q-color a proper family of circular arcs (Q1060020): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| 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 | |||
Latest revision as of 08: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
