Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint

DOI10.1007/978-3-540-68155-7_19MaRDI QIDQ5387633zbMATH OpenOpenAlexFDO

Authors Jean-Charles Régin

Publication date 27 May 2008

Published in Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-68155-7_19

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• The “Not-Too-Heavy Spanning Tree” Constraint
• The Minimum Spanning Tree Constraint
• The Weighted Spanning Tree Constraint Revisited
• Weighted spanning tree constraint with explanations
• The minimum weight spanning tree with constraints

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• Fast Algorithms for Finding Nearest Common Ancestors
• Lowest common ancestors in trees and directed acyclic graphs
• Maintaining Arc Consistency Algorithms During the Search Without Additional Space Cost
• On Finding Lowest Common Ancestors in Trees
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• The tree Constraint
• The “Not-Too-Heavy Spanning Tree” Constraint
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time

Cited in

(8)

• The salesman and the tree: the importance of search in CP
• Improved filtering for weighted circuit constraints
• Weighted spanning tree constraint with explanations
• Counting weighted spanning trees to solve constrained minimum spanning tree problems
• The weighted arborescence constraint
• The “Not-Too-Heavy Spanning Tree” Constraint
• Solving the quorumcast routing problem by constraint programming
• Weighted matching as a generic pruning technique applied to optimization constraints

This page was built for publication: Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint

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