Name
Abstract | ||
|---|---|---|
We present two constraints that partition the vertices of an undirected n-vertex, m-edge graphG = (V;E) into a set of vertex-disjoint trees. The rst is the resource-forest constraint, where we assume that a subset R V of the vertices are resource vertices. The constraint species that each tree in the forest must contain at least one resource vertex. This is the natural undirected counter- part of the tree constraint (1), which partitions a directed graph into a forest of directed trees where only certain vertices can be tree roots. We describe a hy- brid-consistency algorithm that runs inO(m + n) time for the resource-forest constraint, a sharp improvement over theO(mn) bound that is known for the directed case. The second constraint is proper-forest. In this variant, we do not have the requirement that each tree contains a resource, but the forest must con- tain only proper trees, i.e., trees that have at least two vertices each. We develop a hybrid-consistency algorithm for this case whose running time isO(mn) in the worst case, andO(m p n) in many (typical) cases. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11757375_5 | Annals of Operations Research |
Keywords | DocType | Volume |
Constraint programming,Global constraints,Graph partitioning | Conference | 171 |
Issue | ISSN | ISBN |
1 | 0254-5330 | 3-540-34306-7 |
Citations | PageRank | References |
5 | 0.47 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Beldiceanu | 1 | 547 | 51.14 |
| Irit Katriel | 2 | 176 | 13.72 |
| Xavier Lorca | 3 | 330 | 21.03 |