Online Edge Coloring via Tree Recurrences and Correlation Decay
From MaRDI portal
Publication:6203478
DOI10.1137/22M152431XMaRDI QIDQ6203478FDOQ6203478
Authors:
Publication date: 28 February 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Online algorithms; streaming algorithms (68W27) General topics of discrete mathematics in relation to computer science (68R01)
Cites Work
- AdWords and generalized online matching
- The NP-Completeness of Edge-Coloring
- Counting independent sets up to the tree threshold
- Correlation decay up to uniqueness in spin systems
- Improved bounds for sampling colorings
- The greedy algorithm is optimal for on-line edge coloring
- Uniqueness thresholds on trees versus graphs
- Online matching and ad allocation
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Randomized primal-dual analysis of RANKING for online bipartite matching
- Strong Spatial Mixing with Fewer Colors for Lattice Graphs
- Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Spectral independence in high-dimensional expanders and applications to the hardcore model
- Title not available (Why is that?)
- Online graph edge-coloring in the random-order arrival model
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)
