Dulmage-Mendelsohn canonical decomposition as a generic pruning technique

DOI10.1007/S10601-012-9120-4zbMATH Open1309.90116OpenAlexW2048637995MaRDI QIDQ487628FDOQ487628

Authors: Radosław Cymer 

Publication date: 22 January 2015

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-012-9120-4

Recommendations

• Gallai-Edmonds decomposition as a pruning technique
• \(D\)-decomposition technique state-of-the-art
• Canonical trees of tree-decompositions
• scientific article; zbMATH DE number 411827
• Pruning techniques in LinCbO for computation of the Duquenne-Guigues basis
• A generic approach to decomposition algorithms, with an application to digraph decomposition
• Computation of the Canonical Decomposition by Means of a Simultaneous Generalized Schur Decomposition
• scientific article; zbMATH DE number 808812
• scientific article; zbMATH DE number 3942802
• Expander decomposition and pruning: faster, stronger, and simpler

zbMATH Keywords

graph theoryoperations researchconstraint programmingglobal constraintsdecomposition theorymatching theory

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Introduction to algorithms
• Matching theory
• Depth-First Search and Linear Graph Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• A linear-time algorithm for a special case of disjoint set union
• On Representatives of Subsets
• Principles and Practice of Constraint Programming – CP 2004
• TWO THEOREMS IN GRAPH THEORY
• Coverings of Bipartite Graphs
• An Algorithm for a Minimum Cover of a Graph
• Title not available (Why is that?)
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• A permutation-based approach for solving the job-shop problem
• Algorithms for Degree Constrained Graph Factors of Minimum Deficiency
• 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

Cited In (3)

• Title not available (Why is that?)
• Gallai-Edmonds decomposition as a pruning technique
• Weighted matching as a generic pruning technique applied to optimization constraints

This page was built for publication: Dulmage-Mendelsohn canonical decomposition as a generic pruning technique

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