On cuts and matchings in planar graphs

DOI10.1007/BF01580600zbMath0795.90017MaRDI QIDQ688915

Francisco Barahona

Publication date: 1 November 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

planar graphscut polytopemulticommodity flowsmax cut problemoptimum perfect matchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Deterministic network models in operations research (90B10)

Related Items (25)

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods ⋮ Application of cut polyhedra. I ⋮ Improved compact formulations for metric and cut polyhedra ⋮ Solving the max-cut problem using eigenvalues ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ Cuts, matrix completions and graph rigidity ⋮ Graphic vertices of the metric polytope ⋮ Generalized cut and metric polytopes of graphs and simplicial complexes ⋮ A connection between positive semidefinite and Euclidean distance matrix completion problems ⋮ One-third-integrality in the max-cut problem ⋮ Lifting and separation procedures for the cut polytope ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ A compact linear program for testing optimality of perfect matchings. ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Using separation algorithms to generate mixed integer model reformulations ⋮ Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus ⋮ The real positive semidefinite completion problem for series-parallel graphs ⋮ Extended formulations in combinatorial optimization ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Extended formulations in combinatorial optimization ⋮ Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs ⋮ Unnamed Item ⋮ Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• On some weakly bipartite graphs
• Matroids and multicommodity flows
• Compositions in the bipartite subgraph polytope
• Beweis einer Abschwächung der Hadwiger-Vermutung
• A dual ascent approach for steiner tree problems on a directed graph
• The traveling salesman problem in graphs with 3-edge cutsets
• On Odd Cuts and Plane Multicommodity Flows
• Reducing Matching to Polynomial Size Linear Programming
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
• On the cut polytope
• Matching, Euler tours and the Chinese postman
• Maximum matching and a polyhedron with 0,1-vertices
• Feasibility of Two Commodity Network Flows
• Blocking and anti-blocking pairs of polyhedra
• Multi-Commodity Network Flows

This page was built for publication: On cuts and matchings in planar graphs