Some New Matroids on Graphs: Cut Sets and the Max Cut Problem

DOI10.1287/MOOR.12.2.193MaRDI QIDQ3768702zbMATH OpenOpenAlexFDO

Authors

Publication date 1987

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.12.2.193

zbMATH Keywords

edge set of a graphmatroidsminimum weight circuitpolynomial algorithm

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• A construction for binary matroids
• Packing circuits in matroids
• Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
• scientific article; zbMATH DE number 1028231
• A decomposition theory for matroids. IV: Decomposition of graphs

Cited in

(13)

• A construction for binary matroids
• Multiterminal xcut problems
• The cocycle lattice of binary matroids
• On the graphic matroid parity problem
• Computing girth and cogirth in perturbed graphic matroids
• Minimal invariant sets in a vertex-weighted graph
• The equipartition polytope. I: Formulations, dimension and basic facets
• Matroids in terms of Cayley graphs and some related results
• Matroids and Subset Interconnection Design
• scientific article; zbMATH DE number 1757957 (Why is no real title available?)
• Computational complexity analysis of the sensor location flow observability problem
• Integral Polyhedra Related to Even-Cycle and Even-Cut Matroids
• Locating active sensors on traffic networks

This page was built for publication: Some New Matroids on Graphs: Cut Sets and the Max Cut Problem

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