Tree coloring with predictions

DOI10.1016/J.DAM.2025.10.024MaRDI QIDQ6883367zbMATH OpenFDO

Authors Fabian Frei, Matthias Gehnen, Dennis Komm, Rastislav Královič, Richard Královič, Peter Rossmanith, Moritz Stocker

Publication date 16 December 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.10.024

zbMATH Keywords

competitive ratiopredictionsrandom orderonline graph coloring

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Cites work

• scientific article; zbMATH DE number 5776838 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1303205 (Why is no real title available?)
• scientific article; zbMATH DE number 7650400 (Why is no real title available?)
• Advice complexity of online coloring for paths
• Advice complexity of the online coloring problem
• An on-line graph coloring algorithm with sublinear performance ratio
• Competitive Caching with Machine Learned Advice
• Effective coloration
• How Much Information about the Future Is Needed?
• Lower bounds for on-line graph colorings
• On the Advice Complexity of Online Problems
• On-line and first fit colorings of graphs
• Online Computation with Advice
• Online coloring and a new type of adversary for online graph problems
• Online coloring of bipartite graphs with and without advice
• Online computation with untrusted advice
• Online graph coloring with advice and randomized adversary (extended abstract)
• Random-Order Models

This page was built for publication: Tree coloring with predictions

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