Name
Abstract | ||
|---|---|---|
The paper introduces the MST(G,T,W) constraint, which is specified on two graph variables G and T and a vector W of scalar variables. The constraint is satisfied if T is a minimum spanning tree of G, where the edge weights are specified by the entries of W. We develop algorithms that filter the domains of all variables to bound consistency. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11889205_13 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
tree constraint,edge weight,bound consistency,vector w,graph variables g,scalar variable,minimum spanning tree,satisfiability | Discrete mathematics,Combinatorics,Mathematical optimization,Minimum degree spanning tree,Two-graph,Distributed minimum spanning tree,Constraint graph,Spanning tree,Shortest-path tree,Mathematics,Minimum spanning tree,Constrained optimization | Conference |
Volume | ISSN | ISBN |
4204 | 0302-9743 | 3-540-46267-8 |
Citations | PageRank | References |
9 | 0.59 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Grégoire Dooms | 1 | 65 | 5.01 |
| Irit Katriel | 2 | 176 | 13.72 |