Efficient Algorithms for Finding Depth-First and Breadth-First Search Trees in Permutation Graphs

C. Rhee; Y. Daniel Liang; S. K. Dhall; S. Lakshmivarahan

doi:10.1016/0020-0190(94)90053-1

Efficient Algorithms for Finding Depth-First and Breadth-First Search Trees in Permutation Graphs

C. Rhee
, Y. Daniel Liang
, S. K. Dhall
, S. Lakshmivarahan

Computer Science

Research output: Contribution to journal › Article › peer-review

25 Scopus citations

Abstract

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.

Original language	American English
Journal	Information Processing Letters
Volume	44444444444
DOIs	https://doi.org/10.1016/0020-0190(94)90053-1
State	Published - Jan 14 1994

Disciplines

Computer Sciences

Keywords

Algorithms
Breadth-first search
Combinatorial problems
Depth-first search
Permutation graph

Access to Document

10.1016/0020-0190(94)90053-1License: Unspecified

Cite this

@article{470cc0a652ad46f08cbfd3bd616b0495,

title = "Efficient Algorithms for Finding Depth-First and Breadth-First Search Trees in Permutation Graphs",

abstract = " 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. ",

keywords = "Algorithms, Breadth-first search, Combinatorial problems, Depth-first search, Permutation graph",

author = "C. Rhee and Liang, \{Y. Daniel\} and Dhall, \{S. K.\} and S. Lakshmivarahan",

note = "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. View full text",

year = "1994",

month = jan,

day = "14",

doi = "10.1016/0020-0190(94)90053-1",

language = "American English",

volume = "44444444444",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Efficient Algorithms for Finding Depth-First and Breadth-First Search Trees in Permutation Graphs

AU - Rhee, C.

AU - Liang, Y. Daniel

AU - Dhall, S. K.

AU - Lakshmivarahan, S.

N1 - 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. View full text

PY - 1994/1/14

Y1 - 1994/1/14

N2 - 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.

AB - 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.

KW - Algorithms

KW - Breadth-first search

KW - Combinatorial problems

KW - Depth-first search

KW - Permutation graph

UR - https://www.sciencedirect.com/science/article/pii/0020019094900531?via%3Dihub

U2 - 10.1016/0020-0190(94)90053-1

DO - 10.1016/0020-0190(94)90053-1

M3 - Article

SN - 0020-0190

VL - 44444444444

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Efficient Algorithms for Finding Depth-First and Breadth-First Search Trees in Permutation Graphs

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this