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
TypeArticle accepté pour publication ou publié
Journal nameInternational Transactions in Operational Research
MetadataShow full item record
Abstract (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 / KeywordsInterval orders; PQI interval orders; Detection algorithm; Complexity
Showing items related by title and author.