A construction for binary matroids

DOI10.1016/0012-365X(87)90097-5zbMath0644.05017OpenAlexW2012079975MaRDI QIDQ1102297

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 matroidscircuitsgraphic matroidscutsetsEulerian subgraphsbalancing setsT-joinsergodic matroidsminimum weight circuitminimum weight cocircuit

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

Minimizing submodular functions over families of sets, Improving on best-of-many-Christofides for \(T\)-tours, Advances on strictly \(\varDelta \)-modular IPs, Facet identification for the symmetric traveling salesman polytope, 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, Computing girth and cogirth in perturbed graphic matroids, On the complexity of the separation problem for rounded capacity inequalities, The even and odd cut polytopes, A new contraction technique with applications to congruency-constrained cuts, Approximating minimum-cost connected \(T\)-joins

Cites Work

• Unnamed Item
• Decomposition of regular matroids
• On the notion of balance of a signed graph
• Some New Matroids on Graphs: Cut Sets and the Max Cut Problem
• Odd Minimum Cut-Sets and b-Matchings
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• Matching, Euler tours and the Chinese postman
• Lectures on matroids