𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Transitive closure for restricted classes of partial orders

✍ Scribed by Tze-Heng Ma; Jeremy Spinrad

Book ID
104748716
Publisher
Springer Netherlands
Year
1991
Tongue
English
Weight
542 KB
Volume
8
Category
Article
ISSN
0167-8094

No coin nor oath required. For personal study only.

✦ Synopsis

Most papers dealing with partial orders assume that the input is given either in transitively closed or transitrvely reduced form. In this paper, we show that it is possible to solve some problems on partial orders in less time than it takes to perform transitive closure or reduction for general graphs. In particular, we present efficient algorithms for recognizing two dimensional partial orders and N-free partial orders when no assumptions are made about the form of the input.

πŸ“œ SIMILAR VOLUMES

On the calculation of transitive reducti
On the calculation of transitive reductionβ€”closure of orders
✍ M. Habib; M. Morvan; J.-X. Rampon πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 935 KB

Habib, H., M. Morvan and J.-X. Rampon, On the calculation of transitive reduction-closure of orders, Discrete Mathematics 111 (1993) 289-303. Computations of transitive closure and reduction ofdirected acyclic graphs are mainly considered in this paper. Classes of directed acyclic graphs for which