Parallel Algorithms with Optimal Speedup for Bounded Treewidth
From MaRDI portal
Recommendations
Cited in
(71)- A spectral lower bound for the treewidth of a graph and its consequences
- Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
- A parallel algorithm for bisection width in trees
- A unified approach to parallel depth-first traversals of general trees
- Breadth-first traversal of trees and integer sorting in parallel
- Optimal parallel algorithms for forest and term matching
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- A simple optimal parallel algorithm for a core of a tree
- Algorithms for generalized vertex-rankings of partial k-trees
- Reduction algorithms for graphs of small treewidth
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- Structurally parameterized \(d\)-scattered set
- On the impact of treewidth in the computational complexity of freezing dynamics
- Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- On the colored Tutte polynomial of a graph of bounded treewidth
- Boxicity and treewidth
- Bisection of bounded treewidth graphs by convolutions
- Hitting forbidden minors: approximation and kernelization
- A c^k n 5-approximation algorithm for treewidth
- Kernelization -- preprocessing with a guarantee
- Fixed-parameter tractability of treewidth and pathwidth
- A data-parallel algorithm for minimum-width tree layout
- 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
- 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
- OPTIMAL PARALLEL ENCODING AND DECODING ALGORITHMS FOR TREES
- scientific article; zbMATH DE number 1107730 (Why is no real title available?)
- Constructive linear time algorithms for branchwidth
- Parallel algorithms with optimal speedup for bounded treewidth
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Bisection of bounded treewidth graphs by convolutions
- The parallel complexity of tree embedding problems (extended abstract)
- Parameterized (approximate) defective coloring
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- 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
- Fast parallel reordering and isomorphism testing of \(k\)-trees
- Computing LOGCFL certificates
- Efficient parallel algorithms for some tree layout problems
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- Efficient interprocedural data-flow analysis using treedepth and treewidth
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Reduction algorithms for constructing solutions in graphs with small treewidth
- Space efficient algorithm for solving reachability using tree decomposition and separators
- NC-algorithms for graphs with small treewidth
- On the parameterized complexity of freezing dynamics
- Fast parallel hypertree decompositions in logarithmic recursion depth
- Approximation schemes for Min-Sum \(k\)-Clustering
- MSO queries on trees: enumerating answers under updates using forest algebras
- Parameterized algorithms for Steiner forest in bounded width graphs
- Approximation algorithms for the airport and railway problem
- Parameterized algorithms for \textsc{Steiner Forest} in bounded width graphs
- FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
- On the parameterized complexity of computing tree-partitions
- On the parameterized complexity of computing tree-partitions
- Approximation algorithms for the airport and railway problem
- Girth and treewidth
- Minimum stable cut and treewidth
- Dynamic membership for regular tree languages
- Courcelle's theorem for Lipschitz continuity
- I/O-efficient algorithms for graphs of bounded treewidth
- An optimal parallel algorithm forc-vertex-ranking of trees
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)
