Title :
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
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;
Conference_Titel :
Southeastcon '91., IEEE Proceedings of
Conference_Location :
Williamsburg, VA
Print_ISBN :
0-7803-0033-5
DOI :
10.1109/SECON.1991.147822
