Computing treewidth on the GPU

DOI10.4230/LIPIcs.IPEC.2017.29zbMath1443.68213arXiv1709.09990OpenAlexW2760148299MaRDI QIDQ5111889

Tom C. van der Zanden, Hans L. Bodlaender

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1709.09990

zbMATH Keywords

treewidthgraph algorithmsexact algorithmsGPGPUGPUalgorithm engineering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (4)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing treewidth on the GPU

Uses Software

• CUDA
• ComputeTW
• GitHub
• BZTreewidth
• LibTW
• SMHasher
• GPGPU-Treewidth

Cites Work

• Unnamed Item
• Treewidth computations. II. Lower bounds
• Safe separators for treewidth
• Positive-instance driven dynamic programming for treewidth
• On exact algorithms for treewidth
• A Dynamic Programming Approach to Sequencing Problems
• Computing treewidth on the GPU
• Less Hashing, Same Performance: Building a Better Bloom Filter
• Parameterized Algorithms
• Space/time trade-offs in hash coding with allowable errors
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Computing treewidth on the GPU