Transitive closure for restricted classes of partial orders |
| |
Authors: | Tze-Heng Ma Jeremy Spinrad |
| |
Institution: | (1) Institute of Information Science, Academia Sinica, 11529 Nankang, Taipei, Republic of China;(2) Dept. of Computer Science, Vanderbilt U., 37235 Nashville, TN, U.S.A. |
| |
Abstract: | Most papers dealing with partial orders assume that the input is given either in transitively closed or transitively 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.This work was supported by National Science Foundation Grant DCR-8604577 and the Vanderbilt University Research Council. |
| |
Keywords: | 06A06 68Q25 05C85 |
本文献已被 SpringerLink 等数据库收录! |
|