de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45615

Thiel,  Sven
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Mehlhorn, K., & Thiel, S. (2000). Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint. In Principles and practice of constraint programming - CP 2000 (CP-00): 6th international conference, CP 2000 (pp. 306-319). Berlin, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-3344-4
Zusammenfassung
We present narrowing algorithms for the sortedness and the alldifferent constraint which achieve bound-consistency. The algorithm for the sortedness constraint takes as input $2n$ intervals $X_1, \dots, X_n$, $Y_1, \dots, Y_n$ from a linearly ordered set $D$. Let $\mathcal{S}$ denote the set of all tuples $t \in X_1 \times \cdots \times X_n \times Y_1 \times \cdots \times Y_n$ such that the last $n$ components of $t$ are obtained by sorting the first $n$ components. Our algorithm determines whether $\mathcal{S}$ is non-empty and if so reduces the intervals to bound-consistency. The running time of the algorithm is asymptotically the same as for sorting the interval endpoints. In problems where this is faster than $O(n \log n)$, this improves upon previous results. The algorithm for the alldifferent constraint takes as input $n$ integer intervals $Z_1, \dots, Z_n$. Let $\mathcal{T}$ denote all tuples $t \in Z_1 \times \cdots \times Z_n$ where all components are pairwise different. The algorithm checks whether $\mathcal{T}$ is non-empty and if so reduces the ranges to bound-consistency. The running time is also asymptotically the same as for sorting the interval endpoints. When the constraint is for example a permutation constraint, i.e. $Z_i \subseteq \range{1}{n}$ for all $i$, the running time is linear. This also improves upon previous results.