Parallel algorithms for series parallel graphs and graphs with treewidth two

DOI10.1007/s004530010070zbMath0979.05095MaRDI 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 algorithm; treewidth; parallel algorithm; partial \(k\)-tree; series parallel graph; tree decompositions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68W10: Parallel algorithms in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

Efficiently parallelizable problems on a class of decomposable graphs