EFFICIENT ALGORITHMS FOR FINDING DEPTH-FIRST AND BREADTH-FIRST SEARCH-TREES IN PERMUTATION GRAPHS

被引：24

作者：

RHEE, C

LIANG, YD

DHALL, SK

LAKSHMIVARAHAN, S

机构：

[1] UNIV OKLAHOMA,SCH COMP SCI,NORMAN,OK 73019

[2] EASTERN KENTUCKY UNIV,DEPT MATH & COMP SCI,RICHMOND,KY 40475

[3] INDIANA UNIV PURDUE UNIV,DEPT COMP SCI,FT WAYNE,IN 46825

来源：

INFORMATION PROCESSING LETTERS | 1994年 / 49卷 / 01期

关键词：

BREADTH-FIRST SEARCH; DEPTH-FIRST SEARCH; PERMUTATION GRAPH; ALGORITHMS; COMBINATORIAL PROBLEMS;

D O I：

10.1016/0020-0190(94)90053-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper presents an O(n log log n) time algorithm for finding a depth-first search tree and an O(n) time algorithm for finding a breadth-first search tree in a permutation graph, respectively.

引用

页码：45 / 50

页数：6