A construction for binary matroids

DOI10.1016/0012-365X(87)90097-5MaRDI QIDQ1102297zbMATH OpenOpenAlexFDO

Authors Michele Conforti, Francisco Barahona

Publication date 1987

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(87)90097-5

zbMATH Keywords

binary matroidsgraphic matroidscutsetsEulerian subgraphscircuitsbalancing setsT-joinsergodic matroidsminimum weight circuitminimum weight cocircuit

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Some New Matroids on Graphs: Cut Sets and the Max Cut Problem
• Circuit and cocircuit partitions of binary matroids
• The cocycle lattice of binary matroids
• Short cocircuits in binary matroids
• Characterizations of finitary and cofinitary binary matroids

Cites work

• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• Decomposition of regular matroids
• Lectures on matroids
• Matching, Euler tours and the Chinese postman
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• Odd Minimum Cut-Sets and b-Matchings
• On the notion of balance of a signed graph
• Some New Matroids on Graphs: Cut Sets and the Max Cut Problem

Cited in

(17)

• A new contraction technique with applications to congruency-constrained cuts
• Axiomatizing simple binary matroids by their closed circuits
• The cocycle lattice of binary matroids
• Minimizing submodular functions over families of sets
• Facet identification for the symmetric traveling salesman polytope
• Master polytopes for cycles of binary matroids
• scientific article; zbMATH DE number 1003264 (Why is no real title available?)
• A characterization of binary Eulerian matroids
• A construction method of matroidal networks
• Some New Matroids on Graphs: Cut Sets and the Max Cut Problem
• Approximating minimum-cost connected \(T\)-joins
• The even and odd cut polytopes
• Improving on best-of-many-Christofides for \(T\)-tours
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• Advances on strictly \(\varDelta \)-modular IPs
• Computing girth and cogirth in perturbed graphic matroids
• On the complexity of the separation problem for rounded capacity inequalities

This page was built for publication: A construction for binary matroids

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