Zeitschriftenartikel:
J. Maly, S. Woltran:
"Ranking Specific Sets of Objects";
Datenbank Spektrum - Zeitschrift für Datenbanktechnologie und Information Retrieval,
17
(2017),
3;
S. 255
- 265.
Kurzfassung englisch:
Ranking sets of objects based on an order between the single elements has been thoroughly studied in the literature. In particular, it has been shown that it is in general impossible to find a total ranking - jointly satisfying properties as dominance and independence - on the whole power set of objects. However, in many applications certain elements from the entire power set might not be required and can be neglected in the ranking process. For instance, certain sets might be ruled out due to hard constraints or are not satisfying some background theory. In this paper, we treat the computational problem whether an order on a given subset of the power set of elements satisfying different variants of dominance and independence can be found, given a ranking on the elements. We show that this problem is tractable for partial rankings and NP-complete for total rankings.
Schlagworte:
Ranking Sets; Complexity
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/s13222-017-0264-7
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Heterogene Information Integration
Projektleitung Stefan Woltran:
Neue Werkzeuge für graphenbasierte formale Argumentation
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.