Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- 1 December 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (6), 1725-1746
- https://doi.org/10.1137/s0097539795289859
Abstract
No abstract availableThis publication has 32 references indexed in Scilit:
- A partial k-arboretum of graphs with bounded treewidthTheoretical Computer Science, 1998
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthSIAM Journal on Computing, 1996
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of GraphsJournal of Algorithms, 1996
- Improved self-reduction algorithms for graphs with bounded treewidthDiscrete Applied Mathematics, 1994
- An algebraic theory of graph reductionJournal of the ACM, 1993
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- Deterministic parallel list rankingAlgorithmica, 1991
- A simple parallel tree contraction algorithmJournal of Algorithms, 1989
- Complexity of Finding Embeddings in a k-TreeSIAM Journal on Algebraic Discrete Methods, 1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986