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
Cites work
- scientific article; zbMATH DE number 4173002 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 16725 (Why is no real title available?)
- A dual ascent approach for steiner tree problems on a directed graph
- Beweis einer Abschwächung der Hadwiger-Vermutung
- Blocking and anti-blocking pairs of polyhedra
- Compositions in the bipartite subgraph polytope
- Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
- Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
- Feasibility of Two Commodity Network Flows
- Matching, Euler tours and the Chinese postman
- Matroids and multicommodity flows
- Maximum matching and a polyhedron with 0,1-vertices
- Multi-Commodity Network Flows
- On Odd Cuts and Plane Multicommodity Flows
- On some weakly bipartite graphs
- On the cut polytope
- Reducing Matching to Polynomial Size Linear Programming
- The max-cut problem on graphs not contractible to \(K_ 5\)
- The traveling salesman problem in graphs with 3-edge cutsets
Cited in
(33)- Planarizing gadgets for perfect matching do not exist
- 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
- scientific article; zbMATH DE number 7651049 (Why is no real title available?)
- 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
- Improved compact formulations for metric and cut polyhedra
- Extended formulations in combinatorial optimization
- 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
- Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
- Deriving compact extended formulations via LP-based separation techniques
- Distances and cuts in planar graphs
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)
