Skip to main content
Log in

Parallel Algorithms for Maximal Acyclic Sets

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract.

Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in \(O(\log^3 n)\) time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in \(O(\sqrt{n}\log^3n)\) time with O(n 2 ) processors on an EREW PRAM.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

Authors

Additional information

Received July 3, 1995; revised April 1, 1996.

Rights and permissions

Reprints and permissions

About this article

Cite this article

-Z. Chen, Z., He, X. Parallel Algorithms for Maximal Acyclic Sets . Algorithmica 19, 354–368 (1997). https://doi.org/10.1007/PL00009178

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/PL00009178

Navigation