Gallai-Edmonds decomposition as a pruning technique

DOI10.1007/S10100-013-0309-4MaRDI QIDQ301487zbMATH OpenOpenAlexFDO

Authors Radosław Cymer

Publication date 30 June 2016

Published in CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10100-013-0309-4

zbMATH Keywords

constraint programmingglobal constraintsdecomposition theoryextreme setsfiltering algorithmsmatching theory

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Matching models (91B68)

Recommendations

• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• Weighted matching as a generic pruning technique applied to optimization constraints
• Propagation rules for graph partitioning constraints
• Solving various weighted matching problems with constraints
• Recent Advances in Constraints

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1947383 (Why is no real title available?)
• scientific article; zbMATH DE number 2080338 (Why is no real title available?)
• scientific article; zbMATH DE number 2084723 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 3220175 (Why is no real title available?)
• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• A Short Proof of the Factor Theorem for Finite Graphs
• A linear-time algorithm for a special case of disjoint set union
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• An Algorithm for a Minimum Cover of a Graph
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• An algorithm for computing simple \(k\)-factors
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• Global constraints for round robin tournament scheduling.
• Graph factors
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Introducing global constraints in CHIP
• Introduction to algorithms
• Matching structure and the matching lattice
• Paths, Trees, and Flowers
• Principles of Constraint Programming
• TWO THEOREMS IN GRAPH THEORY

Cited in

(4)

• Propagation rules for graph partitioning constraints
• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• A note on extreme sets
• Weighted matching as a generic pruning technique applied to optimization constraints

Describes a project that uses

Uses Software

• SCIL
• LEDA

This page was built for publication: Gallai-Edmonds decomposition as a pruning technique

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