Gallai-Edmonds decomposition as a pruning technique

DOI10.1007/S10100-013-0309-4zbMATH Open1339.90322OpenAlexW1980981969MaRDI QIDQ301487FDOQ301487

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Introduction to algorithms
• Title not available (Why is that?)
• Paths, Trees, and Flowers
• Introducing global constraints in CHIP
• Title not available (Why is that?)
• Title not available (Why is that?)
• A linear-time algorithm for a special case of disjoint set union
• TWO THEOREMS IN GRAPH THEORY
• Principles of Constraint Programming
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• A Short Proof of the Factor Theorem for Finite Graphs
• Matching structure and the matching lattice
• Graph factors
• Global constraints for round robin tournament scheduling.
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• An Algorithm for a Minimum Cover of a Graph
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• An algorithm for computing simple \(k\)-factors

Cited In (3)

• 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

Uses Software

• LEDA
• SCIL

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)