NC algorithms for finding depth-first-search trees in interval graphs and circular-arc graphs

Author

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

Author_Institution

Parallel Process Inst., Oklahoma Univ., Norman, OK, USA

fYear

1991

fDate

7-10 Apr 1991

Firstpage

582

Abstract

Finding depth-first-search (DFS) trees of graphs is one of the fundamental problems in graph theory which has many practical applications. However, there exists no NC parallel algorithm for this problem in general graphs. NC parallel algorithms for finding DFS trees for the interval graphs and circular-arcs graphs are presented. These algorithms take O(log n) time using κn processors on the EREW model, where κ is the number of cliques in a graph of n nodes

Keywords

computational complexity; graph theory; parallel algorithms; search problems; trees (mathematics); EREW model; NC parallel algorithm; circular-arc graphs; cliques; depth-first-search trees; graph theory; interval graphs; Application software; Computer science; Graph theory; Mathematics; Parallel algorithms; Parallel processing; Read-write memory; Spine; Statistics; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Southeastcon '91., IEEE Proceedings of

Conference_Location

Williamsburg, VA

Print_ISBN

0-7803-0033-5

Type

conf

DOI

10.1109/SECON.1991.147822

Filename

147822

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3553972