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

DOI10.1007/S10107-006-0053-9MaRDI QIDQ877189zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Improved algorithms for even factors and square-free simple \(b\)-matchings
• A Combinatorial Algorithm to Find a Maximum Even Factor
• scientific article; zbMATH DE number 5888314
• scientific article; zbMATH DE number 6381750
• scientific article; zbMATH DE number 1342133

Cites work

• An algebraic matching algorithm
• Finding maximum square-free 2-matchings in bipartite graphs
• scientific article; zbMATH DE number 1342133 (Why is no real title available?)
• scientific article; zbMATH DE number 2086910 (Why is no real title available?)
• Minimal edge-coverings of pairs of sets
• Note on the path‐matching formula
• On the maximum even factor in weakly symmetric graphs
• Paths, Trees, and Flowers
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• Restricted \(t\)-matchings in bipartite graphs
• The optimal path-matching problem

Cited in

(21)

• Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs
• Improved algorithms for even factors and square-free simple \(b\)-matchings
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs -- via half-edges
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• A weighted independent even factor algorithm
• Even factors, jump systems, and discrete convexity
• Decomposition theorems for square-free 2-matchings in bipartite graphs
• scientific article; zbMATH DE number 5888314 (Why is no real title available?)
• A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A simple algorithm for finding a maximum triangle-free 2-matching 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
• 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
• Finding triangle-free 2-factors in general graphs
• Finding a maximum restricted t-matching via Boolean edge-CSP
• Finding a maximum restricted \(t\)-matching via Boolean edge-CSP
• A weighted even factor algorithm

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

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