Decomposition and optimization over cycles in binary matroids

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

zbMATH Keywords

algorithmscyclesbinary matroidsLP-relaxationmatroid k-sumsmaximum weight cycle problempolytope k-sums

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

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