On cuts and matchings in planar graphs
From MaRDI portal
Publication:688915
DOI10.1007/BF01580600zbMATH Open0795.90017MaRDI QIDQ688915FDOQ688915
Authors: Francisco Barahona 
Publication date: 1 November 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Recommendations
- Partitioning planar graphs: a fast combinatorial approach for max-cut
- The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
- Perfect matchings versus odd cuts
- Solving matching problems with linear programming
- scientific article; zbMATH DE number 2044946
Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Cites Work
- Title not available (Why is that?)
- Matching, Euler tours and the Chinese postman
- The traveling salesman problem in graphs with 3-edge cutsets
- Maximum matching and a polyhedron with 0,1-vertices
- On the cut polytope
- Blocking and anti-blocking pairs of polyhedra
- Matroids and multicommodity flows
- On Odd Cuts and Plane Multicommodity Flows
- Feasibility of Two Commodity Network Flows
- Multi-Commodity Network Flows
- A dual ascent approach for steiner tree problems on a directed graph
- The max-cut problem on graphs not contractible to \(K_ 5\)
- Compositions in the bipartite subgraph polytope
- Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
- Title not available (Why is that?)
- Beweis einer Abschwächung der Hadwiger-Vermutung
- Title not available (Why is that?)
- Reducing Matching to Polynomial Size Linear Programming
- Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
- On some weakly bipartite graphs
Cited In (33)
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- Lifting and separation procedures for the cut polytope
- A connection between positive semidefinite and Euclidean distance matrix completion problems
- Generalized cut and metric polytopes of graphs and simplicial complexes
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
- Perfect matchings versus odd cuts
- Solving the max-cut problem using eigenvalues
- Extended formulations in combinatorial optimization
- Title not available (Why is that?)
- A compact linear program for testing optimality of perfect matchings.
- Cuts, matrix completions and graph rigidity
- Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Sparsest-cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- One-third-integrality in the max-cut problem
- Application of cut polyhedra. I
- Graphic vertices of the metric polytope
- Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
- Extended formulations in combinatorial optimization
- Improved compact formulations for metric and cut polyhedra
- The real positive semidefinite completion problem for series-parallel graphs
- Using separation algorithms to generate mixed integer model reformulations
- Deriving compact extended formulations via LP-based separation techniques
- Matching cutsets in graphs of diameter 2
- Train and test tightness of LP relaxations in structured prediction
- The cutting plane method is polynomial for perfect matchings
- Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
- Some \(0/1\) polytopes need exponential size extended formulations
- Flow-Cut Gaps and Face Covers in Planar Graphs
- Deriving compact extended formulations via LP-based separation techniques
- Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
- Distances and cuts in planar graphs
- Planarizing gadgets for perfect matching do not exist
This page was built for publication: On cuts and matchings in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688915)
