Trade-offs in dynamic coloring for bipartite and general graphs

DOI10.1007/s00453-022-01050-7OpenAlexW3008044610MaRDI QIDQ2696273

Manas Jyoti Kashyop, N. S. Narayanaswamy, Meghana Nasre, Sai Mohith Potluri

Publication date: 11 April 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1909.07854

zbMATH Keywords

graph coloringdynamic graph algorithms

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Competitive vertex recoloring. (Online disengagement)

Cites Work

• An on-line graph coloring algorithm with sublinear performance ratio
• A data structure for dynamic trees
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Improved Dynamic Graph Coloring
• Fully dynamic maximal independent set with sublinear update time
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Logarithmic Lower Bounds in the Cell-Probe Model
• Decomposition of Finite Graphs Into Forests
• Dynamic graph coloring
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Trade-offs in dynamic coloring for bipartite and general graphs