Parallel Algorithms with Optimal Speedup for Bounded Treewidth
DOI10.1137/S0097539795289859zbMATH Open0907.68089OpenAlexW2017492235MaRDI QIDQ4210129FDOQ4210129
Authors: 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
Recommendations
treewidthgraph algorithmspathwidthderandomizationmonadic second-order logicparallel algorithmstree decompositiongraph reductionpartial \(k\)-trees
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)
Cited In (57)
- Efficient interprocedural data-flow analysis using treedepth and treewidth
- Space efficient algorithm for solving reachability using tree decomposition and separators
- On the parameterized complexity of freezing dynamics
- Approximation schemes for Min-Sum \(k\)-Clustering
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Fast parallel reordering and isomorphism testing of \(k\)-trees
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
- I/O-efficient algorithms for graphs of bounded treewidth
- An optimal parallel algorithm forc-vertex-ranking of trees
- Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
- Title not available (Why is that?)
- Algorithms for generalized vertex-rankings of partial k-trees
- Computing LOGCFL certificates
- Constructive linear time algorithms for branchwidth
- A parallel algorithm for bisection width in trees
- A unified approach to parallel depth-first traversals of general trees
- Optimal parallel algorithms for forest and term matching
- On the colored Tutte polynomial of a graph of bounded treewidth
- A simple optimal parallel algorithm for a core of a tree
- Parallel algorithms with optimal speedup for bounded treewidth
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- A \(c^k n\) 5-approximation algorithm for treewidth
- A data-parallel algorithm for minimum-width tree layout
- Kernelization -- preprocessing with a guarantee
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- Parameterized (approximate) defective coloring
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- Efficient parallel algorithms for some tree layout problems
- Graphs of bounded treewidth can be canonized in AC\(^1\)
- Treewidth computation and kernelization in the parallel external memory model
- Parameterized (approximate) defective coloring
- Enumeration on trees under relabelings
- Bisection of bounded treewidth graphs by convolutions
- Breadth-first traversal of trees and integer sorting in parallel
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
- Optimal parallel generation of a computation tree form
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- A spectral lower bound for the treewidth of a graph and its consequences
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Structurally parameterized \(d\)-scattered set
- OPTIMAL PARALLEL ENCODING AND DECODING ALGORITHMS FOR TREES
- The parallel complexity of tree embedding problems (extended abstract)
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Title not available (Why is that?)
- Boxicity and treewidth
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Girth and treewidth
- Reduction algorithms for graphs of small treewidth
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Recognizing hyperelliptic graphs in polynomial time
- Parallel algorithms for series parallel graphs and graphs with treewidth two
- On the impact of treewidth in the computational complexity of freezing dynamics
- Hitting forbidden minors: approximation and kernelization
- Fixed-parameter tractability of treewidth and pathwidth
This page was built for publication: Parallel Algorithms with Optimal Speedup for Bounded Treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210129)
