TY - GEN
T1 - Parallel algorithms for maximal acyclic sets
AU - Chen, Zhi Zhong
AU - He, Xin
N1 - Publisher Copyright:
© 1995 IEEE.
PY - 1995
Y1 - 1995
N2 - Given a graph G=(V, E), the classical spanning forest problem of G can be viewed as the problem of finding a maximal subset F of E inducing an acyclic subgraph. Although it is well known that this problem has efficient NC algorithms, its vertex counterpart, i.e., the problem of finding a maximal subset U of V inducing an acyclic subgraph, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. We present NC algorithms for solving the latter problem for three special cases. The first algorithm solves the problem for planar graphs in O(log3 n) time using O(n) processors on an EREW PRAM. The second algorithm solves the problem for K3,3-free graphs in O(log4 n) time using O(n) processors on an EREW PRAM. The third algorithm solves the problem for graphs without long induced paths in poly-logarithmic time using O(n2376) processors on an EREW PRAM.
AB - Given a graph G=(V, E), the classical spanning forest problem of G can be viewed as the problem of finding a maximal subset F of E inducing an acyclic subgraph. Although it is well known that this problem has efficient NC algorithms, its vertex counterpart, i.e., the problem of finding a maximal subset U of V inducing an acyclic subgraph, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. We present NC algorithms for solving the latter problem for three special cases. The first algorithm solves the problem for planar graphs in O(log3 n) time using O(n) processors on an EREW PRAM. The second algorithm solves the problem for K3,3-free graphs in O(log4 n) time using O(n) processors on an EREW PRAM. The third algorithm solves the problem for graphs without long induced paths in poly-logarithmic time using O(n2376) processors on an EREW PRAM.
UR - https://www.scopus.com/pages/publications/85027163669
U2 - 10.1109/AISPAS.1995.401341
DO - 10.1109/AISPAS.1995.401341
M3 - Conference contribution
AN - SCOPUS:85027163669
T3 - Proceedings - 1st Aizu International Symposium on Parallel Algorithms/Architecture Synthesis, AISPAS 1995
SP - 169
EP - 175
BT - Proceedings - 1st Aizu International Symposium on Parallel Algorithms/Architecture Synthesis, AISPAS 1995
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1st Aizu International Symposium on Parallel Algorithms/Architecture Synthesis, AISPAS 1995
Y2 - 15 March 1995 through 17 March 1995
ER -