Undirected forest constraints

Nicolas Beldiceanu (), Irit Katriel () and Xavier Lorca ()

Annals of Operations Research, 2009, vol. 171, issue 1, 127-147

Abstract: We present two constraints that partition the vertices of an undirected n-vertex, m-edge graph $\mathcal {G}=( \mathcal {V}, \mathcal {E})$ into a set of vertex-disjoint trees. The first is the resource-forest constraint, where we assume that a subset $\mathcal {R}\subseteq \mathcal {V}$ of the vertices are resource vertices. The constraint specifies that each tree in the forest must contain at least one resource vertex. This is the natural undirected counterpart of the tree constraint (Beldiceanu et al., CP-AI-OR’05, Springer, Berlin, 2005), which partitions a directed graph into a forest of directed trees where only certain vertices can be tree roots. We describe a hybrid-consistency algorithm that runs in $\mathop {\mathcal {O}}(m+n)$ time for the resource-forest constraint, a sharp improvement over the $\mathop {\mathcal {O}}(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 contain 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 is $\mathop {\mathcal {O}}(mn)$ in the worst case, and $\mathop {\mathcal {O}}(m\sqrt{n})$ in many (typical) cases. Copyright Springer Science+Business Media, LLC 2009

Keywords: Constraint programming; Global constraints; Graph partitioning (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-008-0374-6 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:171:y:2009:i:1:p:127-147:10.1007/s10479-008-0374-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-008-0374-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().