Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 279159.0, MPI für Informatik / Algorithms and Complexity Group
Complete Bound Consistency for the Global Cardinality Constraint
Authors:Katriel, Irit; Thiel, Sven
Language:English
Date of Publication (YYYY-MM-DD):2005
Title of Journal:Constraints
Volume:10
Start Page:191
End Page:217
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:We show an algorithm for bound consistency of {\em global cardinality
constraints}, which runs in time $O(n+n')$ plus the time required to
sort the assignment variables by range endpoints, where $n$ is the
number of assignment variables and $n'$ is the number of values in
the union of their domains. It is the first efficient algorithm that
achieves bound consistency for all variables, and not only the
assignment variables.
Last Change of the Resource (YYYY-MM-DD):2006-06-13
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-6450F2ABBE947EF9C1256FAA0043156C-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.