Get all the updates for this publication

Conferences

Data Structures for Incremental Interval ColoringPublished in Springer Verlag

2019

Volume: 11653 LNCS

Pages: 478 - 489

We consider the dynamic graph coloring problem restricted to the class of interval graphs. At each update step the algorithm is presented with an interval to be colored, or a previously colored interval to delete. The goal of the algorithm is to efficiently maintain a proper coloring of the intervals with as few colors as possible by an online algorithm. In the incremental model, each update step presents the algorithm with an interval to be colored. The problem is closely connected to the online vertex coloring problem of interval graphs for which the Kierstead-Trotter (KT) algorithm achieves the best possible competitive ratio. We first show that a sub-quadratic time direct implementation of the KT-algorithm is unlikely to exist conditioned on the correctness of the Online Boolean Matrix Vector multiplication conjecture due to Henzinger et al. [9]. We then design an incremental algorithm that is subtly different from the KT-algorithm and uses at most 3ω − 2 colors, where ω is the maximum clique in the interval graph associated with the set of intervals. Our incremental data structure maintains a proper coloring in amortized O(log n+Δ) update time where n is the total number of intervals inserted and Δ is the maximum degree of a vertex in the interval graph. © Springer Nature Switzerland AG 2019.

Topics: Interval graph (63)%63% related to the paper, Graph coloring (62)%62% related to the paper, Vertex (graph theory) (56)%56% related to the paper, Online algorithm (52)%52% related to the paper and Competitive analysis (52)%52% related to the paper

View more info for "Data Structures for Incremental Interval Coloring"

Content may be subject to copyright.

About the journal

Journal | Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Publisher | Data powered by TypesetSpringer Verlag |

ISSN | 03029743 |

Open Access | No |

Concepts (11)

- COLORING
- Data structures
- BOOLEAN MATRIX-VECTOR MULTIPLICATION
- Competitive ratio
- INCREMENTAL ALGORITHM
- INCREMENTAL DATA
- INCREMENTAL MODELING
- INTERVAL COLORING
- On-line algorithms
- VERTEX COLORING PROBLEMS
- Graph theory