An optimal algorithm for finding depth-first spanning tree on permutation graphs

被引：0
作者：
Sukumar Mondal
Madhumangal Pal
Tapan K. Pal
机构：
[1] Vidyasagar University,Department of Mathematics with Oceanology and Computer Programming
[2] Midnapore College,Department of Mathematics
来源：
Korean Journal of Computational & Applied Mathematics | 1999年 / 6卷 / 3期
关键词：
68Q22; 68Q25; 68R10; Design of algorithms; analysis of algorithms; depth-first-search; spanning tree; permutation graphs;
D O I：
10.1007/BF03009943
中图分类号：
学科分类号：
摘要：
LetG be a connected graph ofn vertices. The problem of finding a depth-first spanning tree ofG is to find a connected subgraph ofG with then vertices andn − 1 edges by depth-first-search. In this paper, we propose anO(n) time algorithm to solve this problem on permutation graphs.
引用
收藏
页码：493 / 500
页数：7
相关论文
共 23 条
[1]  
Even S.(1972)Permutation graphs and transitive graphs J. ACM 19 400-410
[2]  
Pnnueli A.(1971)Transitive orientation of graphs and identification of permutation graphs Canad. J. Math. 23 160-175
[3]  
Lempel A.(1995)On the existence of special depth first search trees J. Graph Theory 19 535-547
[4]  
Even S.(1991)NC algorithms for finding depth first search trees in interval graphs and circular-arc graphs IEEE Proc. SOUTH-EASTCON ’91 1 582-585
[5]  
Pnnueli A.(1994)Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs Information Processing Letters 49 45-50
[6]  
Lempel A.(1995)A new algorithm for minimum spanning tree using depth-first search in an undirected graph Internat. J. Comput. Math. 57 157-161
[7]  
Korach E.(1988)A linear-processor algorithm for depth first search in planar graphs Information Processing Letters 29 119-123
[8]  
Ostfeld Z.(1989)An efficient distributed depth first search algorithm Information Processing Letters 32 183-186
[9]  
Liang Y.(1972)Depth-first search and linear graph algorithms SIAM J. Comput. 1 146-160
[10]  
Rhee C.(undefined)undefined undefined undefined undefined-undefined
123