Parallel Algorithms with Optimal Speedup for Bounded Treewidth

From MaRDI portal
Publication:4210129

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




Related Items (36)

As Time Goes By: Reflections on Treewidth for Temporal GraphsI/O-efficient algorithms for graphs of bounded treewidthA polynomial time algorithm for strong edge coloring of partial \(k\)-treesUnnamed ItemUnnamed ItemKernelization – Preprocessing with a GuaranteeFixed-Parameter Tractability of Treewidth and PathwidthAn Optimal Parallel Algorithm for Minimum Spanning Trees in Planar GraphsBoxicity and treewidthConstructive linear time algorithms for branchwidthBisection of bounded treewidth graphs by convolutionsOn the expressive power of CNF formulas of bounded tree- and clique-widthStructural parameters, tight bounds, and approximation for \((k, r)\)-centerParameterized (Approximate) Defective ColoringA parameterized approximation algorithm for the multiple allocation \(k\)-hub centerGraph Operations Characterizing Rank-Width and Balanced Graph ExpressionsEfficient interprocedural data-flow analysis using treedepth and treewidthSpace efficient algorithm for solving reachability using tree decomposition and separatorsGraphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$Unnamed ItemGirth and treewidthOn the colored Tutte polynomial of a graph of bounded treewidthHitting Forbidden Minors: Approximation and KernelizationRecognizing hyperelliptic graphs in polynomial timeComputing LOGCFL certificatesA (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphsA $c^k n$ 5-Approximation Algorithm for TreewidthLogspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel GraphsUnnamed ItemA spectral lower bound for the treewidth of a graph and its consequencesStructurally parameterized \(d\)-scattered setCharacterizing multiterminal flow networks and computing flows in networks of small treewidthUnnamed ItemAlgorithms for generalized vertex-rankings of partial k-treesReduction algorithms for graphs of small treewidthOn 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