• Media type: Report; E-Book
  • Title: Constrained ordering
  • Contributor: Guttmann, Walter [Author]; Maucher, Markus [Author]
  • imprint: Universität Ulm, 2016-03-14T13:38:44Z
  • Language: English
  • DOI: https://doi.org/10.18725/OPARU-354
  • Keywords: Computational complexity ; Constraint <Künstliche Intelligenz> ; Topological sorting ; Cyclic ordering ; DDC 004 / Data processing & computer science ; NP-completeness ; Total ordering
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.