On the cycle polytope of a binary matroid

DOI10.1016/0095-8956(86)90063-8MaRDI QIDQ1078187zbMATH OpenOpenAlexFDO

Authors Francisco Barahona, Martin Grötschel

Publication date 1986

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(86)90063-8

zbMATH Keywords

binary matroidpolyhedral combinatorics

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Linear programming (90C05)

Recommendations

• Master polytopes for cycles of binary matroids
• Decomposition and optimization over cycles in binary matroids
• Adjacency on combinatorial polyhedra
• On the cardinality constrained matroid polytope
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes

Cites work

• Adjacency on the Postman Polyhedron
• Binary group and Chinese postman polyhedra
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• Matching, Euler tours and the Chinese postman
• Matroids and multicommodity flows
• Maximum matching and a polyhedron with 0,1-vertices
• Some polyhedra related to combinatorial problems
• The max-cut problem on graphs not contractible to \(K_ 5\)

Cited in

(50)

• Solving the prize-collecting rural postman problem
• Decomposition and optimization over cycles in binary matroids
• On a composition of independence systems by circuit identification
• Facets for the cut cone. I
• T-uniqueness of some families of \(k\)-chordal matroids
• Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions
• The generalized arc routing problem
• The periodic rural postman problem with irregular services on mixed graphs
• The undirected capacitated general routing problem with profits
• Pseudocodeword-free criterion for codes with cycle-free Tanner graph
• Master polytopes for cycles of binary matroids
• Application of cut polyhedra. I
• Facets of the \(k\)-partition polytope
• A polyhedral approach to an integer multicommodity flow problem
• Cuboids, a class of clutters
• The Steiner traveling salesman problem and its extensions
• Solving the length constrained K-drones rural postman problem
• Analysis of effective sets of routes for the split-delivery periodic inventory routing problem
• Idealness of \(k\)-wise intersecting families
• Polyhedral analysis and a new algorithm for the length constrained K-drones rural postman problem
• Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization
• On the circuit-spectrum of binary matroids
• Idealness and 2-resistant sets
• Multi-depot rural postman problems
• On the general routing polytope
• Privatized rural postman problems
• Min-Max K-vehicles windy rural postman problem
• Recent results on arc routing problems: an annotated bibliography
• A Semiring on Convex Polygons and Zero-Sum Cycle Problems
• A branch-and-cut algorithm for the maximum benefit Chinese postman problem
• Binary Supersolvable Matroids and Modular Constructions
• scientific article; zbMATH DE number 49899 (Why is no real title available?)
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• Recognizing Even-Cycle and Even-Cut Matroids
• Upgrading edges in the graphical TSP
• The multi‐purpose K‐drones general routing problem
• Chordal matroids arising from generalized parallel connections
• Cycle algebras and polytopes of matroids
• A Branch-and-Cut method for the Capacitated Location-Routing Problem
• Theoretical and computational analysis of a new formulation for the rural postman problem and the general routing problem
• Cardinality minimization, constraints, and regularization: a survey
• The inequicut cone
• The even and odd cut polytopes
• Binary cyclic transversal polytopes
• The multidepot drone general routing problem with duration and capacity constraints
• On the connected blocks polytope
• How is a chordal graph like a supersolvable binary matroid?
• Lower bounds for cube-ideal set-systems
• Minimum cut bases in undirected networks
• A metaheuristic for the min-max windy rural postman problem with K vehicles

This page was built for publication: On the cycle polytope of a binary matroid

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