Large Cuts with Local Algorithms on Triangle-Free Graphs

Problems and results in graph theory and combinatorial analysis

Paul Erdős · 1979

Earlier work this paper cites.

Computers and Intractability: A Guide to the Theory of NP-Completeness

Michael R. Garey and David S. Johnson · 1979

Earlier work this paper cites.

A lower bound on probabilistic algorithms for distributive ring coloring

Moni Naor · 1991

Earlier work this paper cites.

Optimization, approximation, and complexity classes

Christos H. Papadimitriou and Mihalis Yannakakis · 1991

Earlier work this paper cites.

Locality in distributed graph algorithms

Nathan Linial · 1992

Earlier work this paper cites.

A note on bipartite subgraphs of triangle-free graphs

James B. Shearer · 1992

Earlier work this paper cites.

Maximum cuts and largest bipartite subgraphs

Svatopluk Poljak and Zsolt Tuza · 1995

Cited alongside, same era.

Bipartite subgraphs

Noga Alon · 1996

Cited alongside, same era.

Neighborhood graphs and distributed Δ + 1 \Delta+1 -coloring

Pierre Kelsen · 1996

Cited alongside, same era.

Gadgets, approximation, and linear programming

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson · 2000

Cited alongside, same era.

Some optimal inapproximability results

Johan Håstad · 2001

Cited alongside, same era.

On the complexity of distributed graph coloring

Fabian Kuhn and Roger Wattenhofer · 2006

Later among the works it cites.

Distributed computing with advice: information sensitivity of graph coloring

Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc · 2007

Later among the works it cites.

Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007

Later among the works it cites.

Exact bounds for distributed graph colouring

Joel Rybicki · 2011

Later among the works it cites.

Improved exact solver for the weighted Max-SAT problem

Adrian Kügel · 2012

Later among the works it cites.