Online Edge Coloring via Tree Recurrences and Correlation Decay

DOI10.1137/22M152431XMaRDI QIDQ6203478FDOQ6203478

Authors

Publication date 28 February 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

online algorithmsedge coloringcorrelation decaytree recurrences

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) General topics of discrete mathematics in relation to computer science (68R01)

Cites work

• scientific article; zbMATH DE number 6850371 (Why is no real title available?)
• AdWords and generalized online matching
• Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
• Correlation decay up to uniqueness in spin systems
• Counting independent sets up to the tree threshold
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Coupling with the stationary distribution and improved sampling for colorings and independent sets
• Improved bounds for sampling colorings
• Online graph edge-coloring in the random-order arrival model
• Online matching and ad allocation
• Randomized primal-dual analysis of RANKING for online bipartite matching
• Spectral independence in high-dimensional expanders and applications to the hardcore model
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• The NP-Completeness of Edge-Coloring
• The greedy algorithm is optimal for on-line edge coloring
• Uniqueness thresholds on trees versus graphs

This page was built for publication: Online Edge Coloring via Tree Recurrences and Correlation Decay

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