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. We discuss several generalisations and systematically classify the problems. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/978-0-387-34735-6_10 | INTERNATIONAL FEDERATION FOR INFORMATION PROCESSING |
Keywords | DocType | Volume |
total ordering,NP-completeness,computational complexity,betweenness,cyclic ordering,topological sorting | Conference | 209 |
ISSN | Citations | PageRank |
1571-5736 | 21 | 0.90 |
References | Authors | |
8 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Walter Guttmann | 1 | 196 | 16.53 |
Markus Maucher | 2 | 63 | 5.74 |