Combinatorial algorithms for matchings, even factors and square-free 2-factors

DOI10.1007/s10107-006-0053-9zbMath1192.05122OpenAlexW2019720686MaRDI QIDQ877189

Gyula Pap

Publication date: 19 April 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0053-9

zbMATH Keywords

modification of Edmonds' algorithmrestricted matching problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles ⋮ Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids ⋮ Decomposition theorems for square-free 2-matchings in bipartite graphs ⋮ Improved algorithms for even factors and square-free simple \(b\)-matchings ⋮ A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ A weighted independent even factor algorithm ⋮ A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs ⋮ Polyhedron of triangle-free simple 2-matchings in subcubic graphs ⋮ A proof of Cunningham's conjecture on restricted subgraphs and jump systems ⋮ An algorithm for finding a maximum \(t\)-matching excluding complete partite subgraphs ⋮ A weighted even factor algorithm ⋮ Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs ⋮ A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges ⋮ Even factors, jump systems, and discrete convexity ⋮ Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs ⋮ Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the maximum even factor in weakly symmetric graphs
• The optimal path-matching problem
• Restricted \(t\)-matchings in bipartite graphs
• An algebraic matching algorithm
• Minimal edge-coverings of pairs of sets
• Finding maximum square-free 2-matchings in bipartite graphs
• Note on the path‐matching formula
• Paths, Trees, and Flowers

This page was built for publication: Combinatorial algorithms for matchings, even factors and square-free 2-factors