Skip to Main content Skip to Navigation
Reports

Tree-Visibility Orders

Abstract : In this paper we introduce a new class of partially ordered sets, called tree-visibility orders, extending the class of interval orders in a fashion similar to the extension of interval graphs to chordal graphs. This class contains interval orders, duals of generalized interval orders and height one orders. We give a characterization of tree-visibility orders by an infinite family of minimal forbidden suborders and present an efficient recognition algorithm.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074008
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:17:10 PM
Last modification on : Thursday, February 11, 2021 - 2:48:05 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:48:18 PM

Identifiers

  • HAL Id : inria-00074008, version 1

Citation

Dieter Kratsch, Jean-Xavier Rampon. Tree-Visibility Orders. [Research Report] RR-2683, INRIA. 1995. ⟨inria-00074008⟩

Share

Metrics

Record views

186

Files downloads

209