The complexity of tree partitioning
DOI10.1007/s00453-020-00701-xzbMath1453.68120arXiv1704.05896OpenAlexW3014027871MaRDI QIDQ5918926
Ge Xia, Zhao An, Iyad A. Kanj, Qilong Feng
Publication date: 3 September 2020
Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.05896
Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- On the parameterized complexity of computing balanced partitions in graphs
- Machine-based methods in parameterized complexity theory
- A framework for solving VLSI graph layout problems
- Balanced graph partitioning
- On the parameterized complexity of multiple-interval graph problems
- Treewidth. Computations and approximations
- On the lower estimation of non-averaging sets
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Bin packing with fixed number of bins revisited
- An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Balanced partitions of trees and applications
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Genus characterizes the complexity of certain graph problems: Some tight results
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
- A subexponential parameterized algorithm for Subset TSP on planar graphs
- Parameterized Algorithms
This page was built for publication: The complexity of tree partitioning
