首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号