Constrained ordering

Thumbnail
Veröffentlichung
2006-01-13
Authors
Guttmann, Walter
Maucher, Markus
Arbeitspapier


Faculties
Fakultät für Informatik
Series
Ulmer Informatik-Berichte
Abstract
We investigate the problem of finding a total order of a finite set that satisfies various local ordering constraints. Depending on the admitted constraints, we provide an efficient algorithm or prove NP-completeness. To this end, we define a reduction technique and discuss its properties.
Date created
2005
Subject headings
[GND]: Constraint <Künstliche Intelligenz>
[LCSH]: Computational complexity
[Free subject headings]: Cyclic ordering | NP-completeness | Topological sorting | Total ordering
[DDC subject group]: DDC 004 / Data processing & computer science
License
Standard (Fassung vom 03.05.2003)
https://oparu.uni-ulm.de/xmlui/license_v1
Metadata
Show full item record

DOI & citation

Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-354

Guttmann, Walter; Maucher, Markus (2006): Constrained ordering. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. http://dx.doi.org/10.18725/OPARU-354
Citation formatter >