Decomposition and optimization over cycles in binary matroids

DOI10.1016/0095-8956(89)90052-XzbMATH Open0619.05017OpenAlexW2088799722MaRDI QIDQ1089347FDOQ1089347

Authors: 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

Recommendations

• Master polytopes for cycles of binary matroids
• On the cycle polytope of a binary matroid
• A decomposition theory for matroids. I: General results
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• Decomposition of binary matroids

zbMATH Keywords

algorithmsbinary matroidscyclesLP-relaxationmatroid k-sumsmaximum weight cycle problempolytope k-sums

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Decomposition of regular matroids
• Title not available (Why is that?)
• Matching, Euler tours and the Chinese postman
• The ellipsoid method and its consequences in combinatorial optimization
• The traveling salesman problem in graphs with 3-edge cutsets
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• On the cut polytope
• Matroids and multicommodity flows
• Odd Minimum Cut-Sets and b-Matchings
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• The max-cut problem on graphs not contractible to \(K_ 5\)
• On the cycle polytope of a binary matroid
• A decomposition theory for matroids. I: General results
• Title not available (Why is that?)
• An efficient PQ-graph algorithm for solving the graph-realization problem
• An Almost Linear-Time Algorithm for Graph Realization
• Partial matroid representations
• A decomposition theory for matroids. IV: Decomposition of graphs

Cited In (13)

• On the cycle polytope of a binary matroid
• The anti-join composition and polyhedra
• Optimization with binet matrices
• Branch decomposition heuristics for linear matroids
• Compositions for matroids with the Fulkerson property
• Cycle algebras and polytopes of matroids
• Master polytopes for cycles of binary matroids
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• Optimal decompositions of matrices with grades into binary and graded matrices
• The highly connected matroids in minor-closed classes
• Fault-detection in networks
• Title not available (Why is that?)
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs

This page was built for publication: Decomposition and optimization over cycles in binary matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089347)