
A polynomial time algorithm to detect PQI interval orders
Vincke, Philippe; Tsoukiàs, Alexis; Ngo The, An (2000), A polynomial time algorithm to detect PQI interval orders, International Transactions in Operational Research, 7, 6, p. 609-623. http://dx.doi.org/10.1111/j.1475-3995.2000.tb00220.x
View/ Open
Type
Article accepté pour publication ou publiéDate
2000Journal name
International Transactions in Operational ResearchVolume
7Number
6Publisher
Wiley
Pages
609-623
Publication identifier
Metadata
Show full item recordAbstract (EN)
Let S be a PQI preference structure on a finite set A, where the relations P, Q, I stand for 'strict preference', 'weak preference' and 'indifference,' respectively. Two specific preference structures: PQI semi orders and PQI interval orders, have been considered and characterised recently in such a way that is possible to associate to each element of A an interval such that P holds when one interval is completely to the right of the other, I holds when one interval is included to the other and Q holds when one interval is to the right of the other, but they do have a non empty intersection (Q medelling the hesitation). While the detection of a PQI semiorder is straightforward, the case of the PQI interval order is more difficult as the theorem of existence consists in a second-order formula. The paper presents an algorithm for detecting a PQI interval order and demonstrates that it is backtracking free. This result leads to a matrix version of the algorithm which can be proved to be polynomial.Subjects / Keywords
Interval orders; PQI interval orders; Detection algorithm; ComplexityRelated items
Showing items related by title and author.
-
Vincke, Philippe; Tsoukiàs, Alexis (2003) Article accepté pour publication ou publié
-
Ngo The, An; Tsoukiàs, Alexis (2005) Article accepté pour publication ou publié
-
Perny, Patrice; Vincke, Philippe; Tsoukiàs, Alexis (2002) Chapitre d'ouvrage
-
Tsoukiàs, Alexis; Vincke, Philippe (2004) Communication / Conférence
-
Bouyssou, Denis; Marchant, Thierry; Pirlot, Marc; Tsoukiàs, Alexis; Vincke, Philippe (2015) Chapitre d'ouvrage