Parallel algorithms with optimal speedup for bounded treewidth

DOI10.1007/3-540-60084-1_80zbMath1412.68292OpenAlexW1541012495WikidataQ59567987 ScholiaQ59567987MaRDI QIDQ4645184

Torben Hagerup, Hans L. Bodlaender

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/17363

zbMATH Keywords

tree decompositionparallel algorithmfinite indexconflict graphinput graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (8)

Treewidth for graphs with small chordality ⋮ Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension ⋮ Optimal parallel shortest paths in small treewidth digraphs ⋮ Reduction algorithms for constructing solutions in graphs with small treewidth ⋮ On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs ⋮ Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms ⋮ An algorithm for the Tutte polynomials of graphs of bounded treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal parallel algorithms on planar graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Complexity of Finding Embeddings in a k-Tree
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Symmetry-Breaking in Sparse Graphs
• Optimal Parallel 5-Colouring of Planar Graphs
• An algebraic theory of graph reduction
• Bounded Tree-Width and LOGCFL
• A simple parallel tree contraction algorithm
• A linear time algorithm for finding tree-decompositions of small treewidth

This page was built for publication: Parallel algorithms with optimal speedup for bounded treewidth