Decomposition and optimization over cycles in binary matroids
From MaRDI portal
Publication:1089347
DOI10.1016/0095-8956(89)90052-XzbMath0619.05017OpenAlexW2088799722MaRDI QIDQ1089347
Martin Grötschel, Klaus Truemper
Publication date: 1989
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(89)90052-x
algorithmscyclesbinary matroidsLP-relaxationmatroid k-sumsmaximum weight cycle problempolytope k-sums
Related Items (9)
Compositions for matroids with the Fulkerson property ⋮ Cycle algebras and polytopes of matroids ⋮ A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs ⋮ Optimization with binet matrices ⋮ Fault-detection in networks ⋮ The anti-join composition and polyhedra ⋮ Master polytopes for cycles of binary matroids ⋮ The highly connected matroids in minor-closed classes ⋮ A fast algorithm for minimum weight odd circuits and cuts in planar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The max-cut problem on graphs not contractible to \(K_ 5\)
- A decomposition theory for matroids. I: General results
- On the cycle polytope of a binary matroid
- An efficient PQ-graph algorithm for solving the graph-realization problem
- Decomposition of regular matroids
- Matroids and multicommodity flows
- The ellipsoid method and its consequences in combinatorial optimization
- Partial matroid representations
- A decomposition theory for matroids. IV: Decomposition of graphs
- The traveling salesman problem in graphs with 3-edge cutsets
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- An Almost Linear-Time Algorithm for Graph Realization
- Odd Minimum Cut-Sets and b-Matchings
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- On the cut polytope
- Matching, Euler tours and the Chinese postman
This page was built for publication: Decomposition and optimization over cycles in binary matroids
