Computing ears and branchings in parallel
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 464-467
- https://doi.org/10.1109/sfcs.1985.16
Abstract
An ear-decomposition of a digraph is a representation of it as the union of (open or closed) directed paths, each having its endpoints in common with the union of the previous paths but nothing else. We prove that finding an ear-decomposition of a strongly directed graph is in NC, i.e. an eardecomposition can be constructed in parallel in polylog time, using a polynomial number of processors. Using a similar technique, we show that the problem of finding a minimum weight spanning arborescence in an arcweighted rooted digraph is in NC.Keywords
This publication has 4 references indexed in Scilit:
- Ear-decompositions of matching-covered graphsCombinatorica, 1983
- On minimal elementary bipartite graphsJournal of Combinatorial Theory, Series B, 1977
- Optimum branchingsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1967
- Non-separable and planar graphsTransactions of the American Mathematical Society, 1932