Parallel algorithms for series parallel graphs and graphs with treewidth two

DOI10.1007/s004530010070zbMath0979.05095OpenAlexW1993522985MaRDI QIDQ5943662

Hans L. Bodlaender, Babette van Antwerpen-de Fluiter

Publication date: 9 January 2002

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s004530010070

zbMATH Keywords

graph algorithmtreewidthparallel algorithmpartial \(k\)-treeseries parallel graphtree decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (9)

I/O-efficient algorithms for graphs of bounded treewidth ⋮ Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ Series parallel digraphs with loops ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Efficiently parallelizable problems on a class of decomposable graphs ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Unnamed Item ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph

This page was built for publication: Parallel algorithms for series parallel graphs and graphs with treewidth two