On the graphic matroid parity problem

DOI10.1016/S0095-8956(02)00045-XMaRDI QIDQ1400959zbMATH OpenFDO

Authors Zoltán Szigeti

Publication date 17 August 2003

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0095-8956(02)00045-X

zbMATH Keywords

graphic matroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Review text

A new proof is given of the min-max theorem of Lovász on the graphic matroid problem. The proof is based on existing proofs of Tutte's matching theorem. A matroid is graphic if it is the cycle matroid of some graph. Given a graph \(G\) and a partition \(V\) of its edge set into pairs, \((G, V)\) is called a \(v\)-graph, and a \(v\)-forest of \((G, V)\) is a forest of \(G\) consisting of \(v\)-pairs in \(V\). The graphic matroid problem is to find the maximum number of \(v\)-pairs in a \(v\)-forest in a \(v\)-graph.

Recommendations

• A matroid generalization of theorems of Lewin and Gallai
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Structural properties of matroid matchings
• An augmenting path algorithm for linear matroid parity
• Some New Matroids on Graphs: Cut Sets and the Max Cut Problem

Cites work

• A new characterization of the maximum genus of a graph
• Complexity of Matroid Property Algorithms
• Graph factors
• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 1187144 (Why is no real title available?)
• scientific article; zbMATH DE number 3703542 (Why is no real title available?)
• scientific article; zbMATH DE number 3724352 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Matching theory
• Matroid matching and some applications
• Matroid theory and its applications in electric network theory and in statics
• Paths, Trees, and Flowers
• Perfect matchings of a graph
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(12)

• Note on a matroid with parity condition
• The linear delta-matroid parity problem
• Algebraic algorithms for linear matroid parity problems
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• scientific article; zbMATH DE number 3904590 (Why is no real title available?)
• 1.61-approximation for min-power strong connectivity with two power levels
• Optimal hierarchical clustering on a graph
• An improved algorithm for finding maximum outerplanar subgraphs
• Local optimization algorithms for maximum planar subgraph
• On matroid parity and matching polytopes
• A matroid generalization of theorems of Lewin and Gallai
• The parity problem of polymatroids without double circuits

This page was built for publication: On the graphic matroid parity problem

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