Premium
A polynomial time algorithm to detect PQI interval orders
Author(s) -
The A.N.,
Tsoukiàs A.,
Vincke P.
Publication year - 2000
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2000.tb00220.x
Subject(s) - interval (graph theory) , mathematics , intersection (aeronautics) , combinatorics , order (exchange) , preference , discrete mathematics , polynomial , mathematical analysis , statistics , finance , engineering , economics , aerospace engineering
Let S be a P Q I 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: P Q I semi orders and P Q I 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 P Q I semiorder is straightforward, the case of the P Q I interval order is more difficult as the theorem of existence consists in a second‐order formula. The paper presents an algorithm for detecting a P Q I 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.