# zbMATH — the first resource for mathematics

Efficient parallel algorithms for graphs of bounded tree-width. (English) Zbl 0840.68058
Summary: We present an efficient parallel algorithm for the tree-decomposition problem for fixed width $$w$$. The algorithm runs in time $$O(\log^3 n)$$ and uses $$O(n)$$ processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decomposition algorithm is $$O(n\log^2 n)$$. The tree-decomposition algorithm enables us to construct efficient parallel algorithms for a broad class of problems, when restricted to graphs of tree-width at most $$w$$. Many of these problems are NP-complete for general graphs.

##### MSC:
 68W15 Distributed algorithms 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68R10 Graph theory (including graph drawing) in computer science
##### Keywords:
NP-complete problems
Full Text: