inria-00074611, version 1

On-line recognition of interval orders

Vincent Bouchitté, Roland Jégou, Jean-Xavier Rampon ^a, 1

N° RR-2061 (1993)

• a –  Université Rennes I
• 1 :  PAMPA (INRIA - IRISA)
• 
  CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1 France

Références bibliographiques

• Type de publication : Rapports
• Domaine : Informatique/Autre
• Titre : On-line recognition of interval orders
• Résumé : 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.
• Langue du document : Anglais
• Type de rapport : Rapport de recherche
• Date de publication : 1993
• Date de rédaction : 1993
• Référence interne : RR-2061

Liste des fichiers attachés à ce document :

• inria-00074611, version 1
• http://hal.inria.fr/inria-00074611
• oai:hal.inria.fr:inria-00074611
• Contributeur : Rapport De Recherche Inria <>
• Soumis le : Mercredi 24 Mai 2006, 15:53:52
• Dernière modification le : Mardi 13 Mars 2007, 09:22:38