Show simple item record

dc.contributor.authorMaly, Jan
dc.contributor.authorWoltran, Stefan
dc.contributor.editorMitschang, Bernhard
dc.contributor.editorNicklas, Daniela
dc.contributor.editorLeymann, Frank
dc.contributor.editorSchöning, Harald
dc.contributor.editorHerschel, Melanie
dc.contributor.editorTeubner, Jens
dc.contributor.editorHärder, Theo
dc.contributor.editorKopp, Oliver
dc.contributor.editorWieland, Matthias
dc.date.accessioned2017-06-21T11:24:38Z
dc.date.available2017-06-21T11:24:38Z
dc.date.issued2017
dc.identifier.isbn978-3-88579-660-2
dc.identifier.issn1617-5468
dc.description.abstractRanking 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 formalisms from the area of knowledge representation one does not need to order the entire power set, since certain sets are already ruled out due to hard constraints or are not satisfying some background theory. In this paper, we address the question whether an order on a given subset of the power set of elements satisfying different variants of dominance and independence can be found. We first show that this problem is tractable when we look for partial rankings, but becomes NP-complete for total rankings.en
dc.language.isoen
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofDatenbanksysteme für Business, Technologie und Web (BTW 2017) - Workshopband
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-266
dc.subjectRanking Sets. Complexity
dc.titleRanking Specific Sets of Objectsen
dc.typeText/Conference Paper
dc.pubPlaceBonn
mci.reference.pages193-202
mci.conference.sessiontitleWorkshop Präferenzen und Personalisierung in der Informatik (PPI17)
mci.conference.locationStuttgart
mci.conference.date6.-10. März 2017


Files in this item

Thumbnail

Show simple item record