Source author record

Manas Jyoti Kashyop

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Dynamic Data Structures for Interval Coloring

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. \cite{DBLP:conf/stoc/HenzingerKNS15}. 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. We then consider the fully dynamic framework involving insertions and deletions. On each update, our aim is to maintain a $3 ω- 2$ coloring of the remaining set of intervals, where $ω$ is the maximum clique in the interval graph associated with the remaining set of intervals. Our fully dynamic algorithm supports insertion of an interval in $O(\log n + Δ\log ω)$ worst case update time and deletion of an interval in $O(Δ^2 \log n)$ worst case update time.

preprint2020arXiv

Trade-offs in dynamic coloring for bipartite and general graphs

We present trade-offs in the incremental and fully dynamic settings to maintian a proper coloring. For any fully dynamic $2$ -coloring algorithm, the maximum of the update time, number of recolorings, and query time is $Ω(\log n)$ . We present a deterministic fully dynamic $2$ -coloring algorithm with $O(\log^2 n)$ amortized update time, $O(\log n)$ amortized query time, and one recoloring in the worst case. For any incremental $2$ -coloring algorithm which explicitly maintains the color of every vertex after each update, the amortized update time and the amortized number of recolorings is $Ω(\log n)$ . For such an algorithm, in the worst case the update time and the number of recolorings is $Ω(n)$ . We then design a deterministic incremental $2$ -coloring algorithm which explicitly maintains the color of every vertex after each update, with amortized $O(\log n)$ update time and amortized $O(\log n)$ many recolorings. Further, in the worst case the update time and the number of recolorings is $O(n)$ . Further, we present a deterministic incremental $(1+2 \log n)$ -coloring algorithm which explicitly maintains the color of every vertex after each update, with $O(α(n))$ amortized update time, at most one recoloring and $O(1)$ query time. We then show a deterministic incremental $2$ -coloring algorithm which does not maintain color of every vertex after each update, with amortized $O(α(n))$ update time, amortized $O(α(n))$ recolorings, and amortized $O(α(n))$ query time. For general graphs and graphs of bounded arboricity $γ$ and maximum degree $Δ$ we present a deterministic $(Δ+1)$ -coloring algorithm with $O(\sqrt{m})$ update time, $O(1)$ query time, and one recoloring. Finally, we show a deterministic $(Δ+1)$ -coloring algorithm with amortized $O(γ+ \log{n})$ update time, $O(1)$ query time, and one recoloring.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.