Dynamic graph coloring

DOI10.1007/s00453-018-0473-yzbMath1423.05059OpenAlexW2962923099MaRDI QIDQ5915986

Luis Barba, Jean Cardinal, Matias Korman, Sander Verdonschot, Marcel Roeloffzen, Stefan Langerman, André van Renssen

Publication date: 25 April 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0473-y

zbMATH Keywords

graphsdata structuresdynamic coloringamortized algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Competitive vertex recoloring. (Online disengagement) ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fully-dynamic min-cut
• An on-line graph coloring algorithm with sublinear performance ratio
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• Lower bounds for on-line graph coloring
• Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
• Fully dynamic randomized algorithms for graph spanners
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Decomposable searching problems I. Static-to-dynamic transformation
• Randomized online graph coloring
• Parallel and On-Line Graph Coloring
• Simple heuristics for unit disk graphs
• Reducibility among Combinatorial Problems
• Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Dynamic graph connectivity in polylogarithmic worst case time
• Dynamic graph coloring

This page was built for publication: Dynamic graph coloring