Parallel Algorithms with Optimal Speedup for Bounded Treewidth

DOI10.1137/S0097539795289859zbMath0907.68089OpenAlexW2017492235MaRDI QIDQ4210129

Torben Hagerup, Hans L. Bodlaender

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795289859

zbMATH Keywords

monadic second-order logictreewidthparallel algorithmstree decompositiongraph algorithmspathwidthderandomizationgraph reductionpartial \(k\)-trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (36)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ I/O-efficient algorithms for graphs of bounded treewidth ⋮ A polynomial time algorithm for strong edge coloring of partial \(k\)-trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs ⋮ Boxicity and treewidth ⋮ Constructive linear time algorithms for branchwidth ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ On the expressive power of CNF formulas of bounded tree- and clique-width ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Parameterized (Approximate) Defective Coloring ⋮ A parameterized approximation algorithm for the multiple allocation \(k\)-hub center ⋮ Graph Operations Characterizing Rank-Width and Balanced Graph Expressions ⋮ Efficient interprocedural data-flow analysis using treedepth and treewidth ⋮ Space efficient algorithm for solving reachability using tree decomposition and separators ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ Unnamed Item ⋮ Girth and treewidth ⋮ On the colored Tutte polynomial of a graph of bounded treewidth ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ Computing LOGCFL certificates ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs ⋮ Unnamed Item ⋮ A spectral lower bound for the treewidth of a graph and its consequences ⋮ Structurally parameterized \(d\)-scattered set ⋮ Characterizing multiterminal flow networks and computing flows in networks of small treewidth ⋮ Unnamed Item ⋮ Algorithms for generalized vertex-rankings of partial k-trees ⋮ Reduction algorithms for graphs of small treewidth ⋮ On the impact of treewidth in the computational complexity of freezing dynamics

This page was built for publication: Parallel Algorithms with Optimal Speedup for Bounded Treewidth