Cycle-free partial orders and chordal comparability graphs |
| |
Authors: | Tze-Heng Ma Jeremy P Spinrad |
| |
Institution: | (1) Institute of Information Science, Academia Sinica, Nankang, 11529 Taipei, People's Republic of China;(2) Department of Computer Science, Vanderbilt University, 37235 Nashville, TN, USA |
| |
Abstract: | This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n
2) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m
t)time, where m
tis the number of edges in the transitive closure. |
| |
Keywords: | Primary 06A06 secondary 05C20 68Q25 |
本文献已被 SpringerLink 等数据库收录! |
|