Skip to Main content Skip to Navigation
Reports

On-line recognition of interval orders

Abstract : The first one is optimal in time and space and recognizes the transitive closure of an interval order under the suborder hypothesis which means that we add a new element to the transitive closure of an interval order and test if the new digraph is always the transitive closure of an interval order. The second one recognizes the transitive reduction of an interval order in linear space and almost linear time under the linear extension hypothesis which means that we add a new maximal element to the transitive reduction of an interval order.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074611
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 3:53:52 PM
Last modification on : Thursday, February 11, 2021 - 2:48:05 PM
Long-term archiving on: : Monday, April 5, 2010 - 12:12:13 AM

Identifiers

  • HAL Id : inria-00074611, version 1

Citation

Vincent Bouchitté, Roland Jégou, Jean-Xavier Rampon. On-line recognition of interval orders. [Research Report] RR-2061, INRIA. 1993. ⟨inria-00074611⟩

Share

Metrics

Record views

249

Files downloads

250