Efficient Parallel Algorithms for Graphs of Bounded Tree-Width Export

@article{citeulike:2831062, abstract = {We present an efficient parallel algorithm for the tree-decomposition problem for fixed widthw. The algorithm runs in time (log3 n) and uses (n) processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decomposition algorithm is (n log2 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 mostw. Many of these problems areNP-complete for general graphs.}, author = {Lagergren, Jens}, citeulike-article-id = {2831062}, citeulike-linkout-0 = {http://dx.doi.org/10.1006/jagm.1996.0002}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6WH3-45MH2GB-1X/1/b3007486db71a89111fb84ad2551df9b}, doi = {10.1006/jagm.1996.0002}, journal = {Journal of Algorithms}, keywords = {tree\_decomposition}, month = {January}, number = {1}, pages = {20--44}, posted-at = {2008-05-25 18:24:18}, priority = {4}, title = {Efficient Parallel Algorithms for Graphs of Bounded Tree-Width}, url = {http://dx.doi.org/10.1006/jagm.1996.0002}, volume = {20}, year = {1996} }

TY - JOUR ID - citeulike:2831062 L3 - citeulike-article-id:2831062 N2 - We present an efficient parallel algorithm for the tree-decomposition problem for fixed widthw. The algorithm runs in time (log3 n) and uses (n) processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decomposition algorithm is (n log2 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 mostw. Many of these problems areNP-complete for general graphs. IS - 1 JF - Journal of Algorithms EP - 44 TI - Efficient Parallel Algorithms for Graphs of Bounded Tree-Width VL - 20 SP - 20 KW - tree_decomposition AU - Lagergren, Jens PY - 1996/01// UR - http://dx.doi.org/10.1006/jagm.1996.0002 ER -