✦ LIBER ✦

A probabilistic result for the max-cut problem on random graphs

✍ Scribed by Amir Beck; Marc Teboulle

Book ID: 108410421
Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 101 KB
Volume: 27
Category: Article
ISSN: 0167-6377
DOI: 10.1016/s0167-6377(00)00055-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Some New Matroids on Graphs: Cut Sets an

Some New Matroids on Graphs: Cut Sets and the Max Cut Problem

✍ Michele Conforti and M. R. Rao 📂 Article 📅 1987 🏛 INFORMS 🌐 English ⚖ 494 KB

A polynomial algorithm for the max-cut p

A polynomial algorithm for the max-cut problem on graphs without long odd cycles

✍ Martin Grötschel; George L. Nemhauser 📂 Article 📅 1984 🏛 Springer-Verlag 🌐 English ⚖ 707 KB

The max-cut problem on graphs not contra

The max-cut problem on graphs not contractible to K5

✍ Francisco Barahona 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 454 KB

An effective compact formulation of the

An effective compact formulation of the max cut problem on sparse graphs

✍ Giuseppe Lancia; Paolo Serafini 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 142 KB

Complexity results for the gap inequalit

Complexity results for the gap inequalities for the max-cut problem

✍ Laura Galli; Konstantinos Kaparis; Adam N. Letchford 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 240 KB

On the max-cut problem for a planar, cub

On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation

✍ Carsten Thomassen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/24 − 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Example