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 programmingdecomposition theoryextreme setsfiltering algorithmsglobal constraintsmatching theory

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Convex programming (90C25) Programming involving graphs or networks (90C35) 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

• A linear-time algorithm for a special case of disjoint set union
• A Short Proof of the Factor Theorem for Finite Graphs
• 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 algorithm for computing simple \(k\)-factors
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• 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
• 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?)
• 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)

• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• Weighted matching as a generic pruning technique applied to optimization constraints
• A note on extreme sets
• Propagation rules for graph partitioning 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)