On the parameterized complexity of computing tree-partitions

DOI10.4230/LIPICS.IPEC.2022.7MaRDI QIDQ6969005zbMATH OpenFDO

Authors Hans L. Bodlaender, Carla Groenland, H. Jacob

Publication date 23 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2022.7

zbMATH Keywords

approximation algorithmsdomino treewidthparameterized algorithmsparameterized complexitytree partitionstree-partition-widthtreewidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A single-exponential time 2-approximation algorithm for treewidth
• Algorithmic applications of tree-cut width
• Computing straight-line 3D grid drawings of graphs in linear volume
• Distinct distances in graph drawings
• Domino Treewidth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Graph drawings with few slopes
• scientific article; zbMATH DE number 3917707 (Why is no real title available?)
• scientific article; zbMATH DE number 1375581 (Why is no real title available?)
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Layout of Graphs with Bounded Tree-Width
• Maximal Flow Through a Network
• Notes on nonrepetitive graph colouring
• On the parameterized complexity of computing tree-partitions
• On tree-partition-width
• On tree-partitions of graphs
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Partitioning into graphs with only small components
• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Some results on tree decomposition of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The structure of graphs not admitting a fixed immersion
• Towards tight(er) bounds for the excluded grid theorem
• Tree-partitions of infinite graphs
• Undirected connectivity in log-space

Cited in

(4)

• Product structure of graph classes with strongly sublinear separators
• The parameterised complexity of integer multicommodity flow
• On the parameterized complexity of computing tree-partitions
• On the complexity of problems on tree-structured graphs

This page was built for publication: On the parameterized complexity of computing tree-partitions

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