Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
From MaRDI portal
Publication:2672420
DOI10.1007/978-3-030-86838-3_2OpenAlexW3202445239MaRDI QIDQ2672420
Publication date: 8 June 2022
Full work available at URL: https://arxiv.org/abs/2012.01226
Related Items
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- The complexity of finding uniform emulations on paths and ring networks
- On problems without polynomial kernels
- The NP-completeness of the bandwidth minimization problem
- Bandwidth and density for block graphs
- The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete
- Parametrized complexity theory.
- Beyond NP-completeness for problems of bounded width (extended abstract)
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- New Limits to Classical and Quantum Instance Compression
- Simulation of large networks on smaller networks
- Quotient Networks
- The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Collaborating with Hans: Some Remaining Wonderments
- Parameterized Complexity of Bandwidth on Trees
