• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
Itor24.pdf (156.2Kb)
Type
Article accepté pour publication ou publié
Date
2000
Journal name
International Transactions in Operational Research
Volume
7
Number
6
Publisher
Wiley
Pages
609-623
Publication identifier
http://dx.doi.org/10.1111/j.1475-3995.2000.tb00220.x
Metadata
Show full item record
Author(s)
Vincke, Philippe
Tsoukiàs, Alexis cc
Ngo The, An
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 / Keywords
Interval orders; PQI interval orders; Detection algorithm; Complexity

Related items

Showing items related by title and author.

  • Thumbnail
    A characterization of PQI interval orders 
    Vincke, Philippe; Tsoukiàs, Alexis (2003) Article accepté pour publication ou publié
  • Thumbnail
    Numerical representation of PQI interval orders 
    Ngo The, An; Tsoukiàs, Alexis (2005) Article accepté pour publication ou publié
  • Thumbnail
    From Concordance/Discordance to the Modelling of Positive and Negative Reasons in Decision Aiding 
    Perny, Patrice; Vincke, Philippe; Tsoukiàs, Alexis (2002) Chapitre d'ouvrage
  • Thumbnail
    Preferences On Intervals: a general framework 
    Tsoukiàs, Alexis; Vincke, Philippe (2004) Communication / Conférence
  • Thumbnail
    Aiding to decide: concepts and issues 
    Bouyssou, Denis; Marchant, Thierry; Pirlot, Marc; Tsoukiàs, Alexis; Vincke, Philippe (2015) Chapitre d'ouvrage
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo