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

balancing setsbinary matroidscircuitscutsetsergodic matroidsEulerian subgraphsgraphic matroidsminimum weight circuitminimum weight cocircuitT-joins

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Review text

A family of subsets of a ground set closed under the operation of taking symmetric differences is the family of cycles of a binary matroid, whose circuits are the minimal members of this collection. Using this fact two binary matroids are derived from graphic and ergodic matroids. Cocycles of the first one are cutsets or balancing sets. Cocycles of the second one are Eulerian subgraphs or T-joins. Then the problem of finding a minimum weight circuit and cocircuit in these matroids is studied.

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

• Decomposition of regular matroids
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• 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

(18)

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

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)