Cut polytopes of minor-free graphs
| Autor(en): | Chimani, Markus Juhnke-kubitzke, Martina Nover, Alexander Roemer, Tim |
Stichwörter: | combinatorial optimization; cut polytope; FACETS; graph; lattice polytope; Mathematics; MAX-CUT; Maximum cut; polyhedral study | Erscheinungsdatum: | 2023 | Herausgeber: | SOC MATEMATICE ROMANIA | Journal: | BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE | Volumen: | 66 | Ausgabe: | 1 | Startseite: | 97 | Seitenende: | 112 | Zusammenfassung: | The cut polytope of a graph G is the convex hull of the indicator vectors of all cuts in G and is closely related to the MAxCUT problem. We give the facet-description of cut polytopes of K-3,K-3-minor-free graphs and introduce an algorithm solving MAxCUT on those graphs, which only requires the running time of planar MAxCUT. Moreover, starting a systematic geometric study of cut polytopes, we classify graphs admitting a simple or simplicial cut polytope. |
ISSN: | 1220-3874 |
Zur Langanzeige
