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.

68W15 Distributed algorithms
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI