Competitive capacitated online recoloring

DOI10.4230/LIPICS.ESA.2024.95MaRDI QIDQ7253164zbMATH OpenFDO

Authors Rajmohan Rajaraman, Omer Wasim

Publication date 26 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2024.95

zbMATH Keywords

competitive ratioonline algorithmsrecoloringresource augmentation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A fast algorithm for equitable coloring
• Competitive vertex recoloring
• Constant-time Dynamic (Δ +1)-Coloring
• Demand-aware network designs of bounded degree
• Dynamic balanced graph partitioning
• Dynamic graph coloring
• Fully Dynamic (Δ +1)-Coloring in O (1) Update Time
• scientific article; zbMATH DE number 7759285 (Why is no real title available?)
• scientific article; zbMATH DE number 7788504 (Why is no real title available?)
• Improved bounds for online balanced graph re-partitioning
• Improved dynamic graph coloring
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Trade-offs in dynamic coloring for bipartite and general graphs

Cited in

(1)

• Colorful vertex recoloring of bipartite graphs

This page was built for publication: Competitive capacitated online recoloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253164)