The optimal path-matching problem

DOI10.1007/BF01215915zbMath0902.05056OpenAlexW3160322950MaRDI QIDQ1272178

James F. Geelen, William H. Cunningham

Publication date: 23 November 1998

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01215915

zbMATH Keywords

matroidpath-matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (14)

Matroid bases with cardinality constraints on the intersection ⋮ Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ On the maximum even factor in weakly symmetric graphs ⋮ Combinatorial algorithms for matchings, even factors and square-free 2-factors ⋮ Improved algorithms for even factors and square-free simple \(b\)-matchings ⋮ A weighted independent even factor algorithm ⋮ Matchings of cycles and paths in directed graphs ⋮ A weighted even factor algorithm ⋮ Facets of the independent path-matching polytope ⋮ Algebraic Algorithms for Linear Matroid Parity Problems ⋮ Even factors, jump systems, and discrete convexity ⋮ Spectral aspects of symmetric matrix signings ⋮ Spectral aspects of symmetric matrix signings ⋮ Length-constrained path-matchings in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• The perfectly matchable subgraph polytope of an arbitrary graph
• Short proofs on the matching polyhedron
• The ellipsoid method and its consequences in combinatorial optimization
• A separation algorithm for the matchable set polytope
• Odd Minimum Cut-Sets and b-Matchings
• Paths, Trees, and Flowers
• Transversals and matroid partition
• Maximum matching and a polyhedron with 0,1-vertices
• Systems of distinct representatives and linear algebra
• The Factorization of Linear Graphs

This page was built for publication: The optimal path-matching problem