Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
From MaRDI portal
Publication:4864433
DOI10.1006/JAGM.1996.0002zbMATH Open0840.68058OpenAlexW2010600799MaRDI QIDQ4864433FDOQ4864433
Authors: Jens Lagergren 
Publication date: 20 February 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1996.0002
Recommendations
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Parallel algorithms with optimal speedup for bounded treewidth
- Efficient parallel algorithms for breadth first spanning forests of general graphs
- Parallel breadth-first search algorithms for trees and graphs
- Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
- scientific article; zbMATH DE number 54593
- Efficient parallel algorithms for some tree layout problems
- scientific article; zbMATH DE number 3972201
- Parallel algorithms for series parallel graphs and graphs with treewidth two
- Parallel search algorithms for graphs and trees
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)
Cited In (40)
- Efficient parallel algorithms for parameterized problems
- I/O-efficient algorithms for graphs of bounded treewidth
- I/O-efficient algorithms for graphs of bounded treewidth
- Title not available (Why is that?)
- Computing LOGCFL certificates
- A parallel algorithm for bisection width in trees
- A sufficiently fast algorithm for finding close to optimal clique trees
- Parallel algorithms with optimal speedup for bounded treewidth
- Graph minors and parameterized algorithm design
- On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
- Title not available (Why is that?)
- A \(c^k n\) 5-approximation algorithm for treewidth
- Space-efficient vertex separators for treewidth
- Online promise problems with online width metrics
- A data-parallel algorithm for minimum-width tree layout
- Un algorithme parallèle efficace pour construire un arbre de poids minimal dans un graphe
- Efficiently parallelizable problems on a class of decomposable graphs
- Finding small-width connected path decompositions in polynomial time
- Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
- Efficient parallel algorithms for some tree layout problems
- Treewidth computation and kernelization in the parallel external memory model
- NC-algorithms for graphs with small treewidth
- Treewidth computations. I: Upper bounds
- Title not available (Why is that?)
- Counting \(H-\)colorings of partial \(k-\)trees
- Approximation algorithms for digraph width parameters
- An improvement of Reed's treewidth approximation
- An improvement of Reed's treewidth approximation
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- The parallel complexity of tree embedding problems (extended abstract)
- An improved parameterized algorithm for treewidth
- A simple parallel algorithm for computing the diameters of all vertices in a tree and its application
- Tree decompositions and social graphs
- An improved algorithm for finding tree decompositions of small width
- An optimal parallel processor bound in strong orientation of an undirected graph
- Reduction algorithms for graphs of small treewidth
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- Title not available (Why is that?)
- Typical sequences revisited -- computing width parameters of graphs
- Fixed-parameter tractability of treewidth and pathwidth
This page was built for publication: Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4864433)
