This paper places three greedy search problems in the class NC: lexicographic topological-first search (lex-tfs) for DAGs, lexicographic depth-first search (lex-dfs) for DAGs, and lexicographic breadth-first search (lex-bfs) for directed graphs. The latter result answers an open question of Hoover and Ruzzo (A compendium of problems complete for P, draft, November 1985). For each of these problems, we show that the search trees from all sources in a graph of n vertices can be computed by an EREW PRAM in O(log(2) n) time using O(n(3)) operations for lex-dfs and O(n(3) log n) operations for lex-bfs/lex-tfs. Two novel results that emerge from our derivation of the algorithms are of interest in their own right. One uncovers a natural correspondence between the greedy search strategies and lexicographic versions of path finding problems. The other result is our approach to generating parallel algorithms for the lexicographic versions of path-algebra problems in a uniform way. This approach gives rise to a unifying algorithm which yields, as particular cases, NC algorithms for the path problems that correspond to the three greedy search strategies: all-pairs lexmax longest paths for weighted DAGs, all-pairs lexmin paths for DAGs, and all-pairs lexmin shortest paths for weighted directed graphs with no cycles of negative cost. (C) 1995 Academic Press, Inc. [References: 36]
展开▼
