Paper Info
Title
Simpler and incremental consistency checking and arc consistency filtering algorithms for the weighted spanning tree constraint
Abstract
The weighted spanning tree contraint is defined from a set of variables X and a value K. The variables X represent the nodes of a graph and the domain of a variable x ∈ X the neighbors of the node in the graph. In addition each pair (variable, value) is associated with a cost. This constraint states that the graph defined from the variables and the domains of the variables admits a spanning tree whose cost is less than K. Efficient algorithms to compute a minimum spanning tree or to establish arc consistency of this constraint have been proposed. However, these algorithms are based on complex procedures that are rather difficult to understand and to implement. In this paper, we propose and detail simpler algorithms for checking the consistency of the constraint and for establishing arc consistency. In addition, we propose for the first time incremental algorithms for this constraint, that is algorithms that have been designed in order to be efficiently maintained during the search for solution.
Year
DOI
Venue
2008
10.1007/978-3-540-68155-7_19
CPAIOR
Keywords
Field
DocType
k. efficient algorithm,arc consistency,tree contraint,tree constraint,detail simpler algorithm,incremental consistency checking,time incremental algorithm,constraint state,complex procedure,value k.,variables x,spanning tree,minimum spanning tree
Discrete mathematics,Local consistency,Mathematical optimization,k-minimum spanning tree,Computer science,Algorithm,Euclidean minimum spanning tree,Connected dominating set,Spanning tree,Constraint logic programming,Kruskal's algorithm,Minimum spanning tree
Conference
Volume
ISSN
ISBN
5015
0302-9743
3-540-68154-X
Citations 
PageRank 
References 
8
0.57
13
Authors
1
Name
Order
Citations
PageRank
Jean-charles Régin1131296.59