NC-algorithms for graphs with small treewidth

DOI10.1007/3-540-50728-0_32MaRDI QIDQ6203537zbMATH OpenOpenAlexWikidataFDO

Authors Hans L. Bodlaender

Publication date 28 February 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/16558

Mathematics Subject Classification ID

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)

Recommendations

• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Parallel algorithms with optimal speedup for bounded treewidth
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• scientific article; zbMATH DE number 1107730
• Parallel algorithms for series parallel graphs and graphs with treewidth two

Cites work

• Complexity of Finding Embeddings in a k-Tree
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3837386 (Why is no real title available?)
• scientific article; zbMATH DE number 4024784 (Why is no real title available?)
• scientific article; zbMATH DE number 4062614 (Why is no real title available?)
• scientific article; zbMATH DE number 4081531 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Parallel O(log n) time edge-colouring of trees and Halin graphs

Cited in

(9)

• Balancing bounded treewidth circuits
• On treewidth, separators and Yao's garbling
• Algorithms, Complexity, and Hans
• On reduction algorithms for graphs with small treewidth
• The telephone k-multicast problem
• Polylogarithmic approximations for robust s-t path
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
• Degrees and network design: new problems and approximations
• Approximating sparsest cut in low-treewidth graphs via combinatorial diameter

This page was built for publication: NC-algorithms for graphs with small treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203537)