Parallel Algorithms with Optimal Speedup for Bounded Treewidth
From MaRDI portal
Publication:4210129
Recommendations
Cited in
(59)- 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
- Fast parallel reordering and isomorphism testing of \(k\)-trees
- Optimal parallel algorithms for constructing and maintaining a balanced m-way search tree
- scientific article; zbMATH DE number 7525479 (Why is no real title available?)
- Algorithms for generalized vertex-rankings of partial k-trees
- A unified approach to parallel depth-first traversals of general trees
- Optimal parallel algorithms for forest and term matching
- A parallel algorithm for bisection width in trees
- Constructive linear time algorithms for branchwidth
- Computing LOGCFL certificates
- A simple optimal parallel algorithm for a core of a tree
- On the colored Tutte polynomial of a graph of bounded treewidth
- Parallel algorithms with optimal speedup for bounded treewidth
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- A \(c^k n\) 5-approximation algorithm for treewidth
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- 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
- Efficient interprocedural data-flow analysis using treedepth and treewidth
- Parameterized (approximate) defective coloring
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- Graphs of bounded treewidth can be canonized in AC\(^1\)
- Treewidth computation and kernelization in the parallel external memory model
- Efficient parallel algorithms for some tree layout problems
- Parameterized (approximate) defective coloring
- NC-algorithms for graphs with small treewidth
- Space efficient algorithm for solving reachability using tree decomposition and separators
- 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
- 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
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- Structurally parameterized \(d\)-scattered set
- OPTIMAL PARALLEL ENCODING AND DECODING ALGORITHMS FOR TREES
- The parallel complexity of tree embedding problems (extended abstract)
- On the parameterized complexity of freezing dynamics
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Girth and treewidth
- Boxicity and treewidth
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Reduction algorithms for graphs of small treewidth
- Approximation schemes for Min-Sum \(k\)-Clustering
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Recognizing hyperelliptic graphs in polynomial time
- Reduction algorithms for constructing solutions in graphs with small treewidth
- Fast parallel hypertree decompositions in logarithmic recursion depth
- On the impact of treewidth in the computational complexity of freezing dynamics
- Parallel algorithms for series parallel graphs and graphs with treewidth two
- 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)
