Large cuts with local algorithms on triangle-free graphs
From MaRDI portal
Publication:2411507
zbMath1373.05189arXiv1402.2543MaRDI QIDQ2411507
Stefan Schmid, Jukka Suomela, Joel Rybicki, Juho Hirvonen
Publication date: 24 October 2017
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1402.2543
Related Items (5)
Fast Distributed Approximation for Max-Cut ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Unnamed Item ⋮ Local approximation of the maximum cut in regular graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ramanujan graphs
- Optimization, approximation, and complexity classes
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Bipartite subgraphs
- Survey of local algorithms
- Exact Bounds for Distributed Graph Colouring
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Locality in Distributed Graph Algorithms
- A note on bipartite subgraphs of triangle‐free graphs
- Gadgets, Approximation, and Linear Programming
- Neighborhood graphs and distributed Δ+1-coloring
- On the complexity of distributed graph coloring
- Distributed Computing with Advice: Information Sensitivity of Graph Coloring
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
This page was built for publication: Large cuts with local algorithms on triangle-free graphs
