Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}

DOI10.1007/978-3-030-86838-3_2OpenAlexW3202445239MaRDI QIDQ2672420

Hans L. Bodlaender

Publication date: 8 June 2022

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

zbMATH Keywords

bandwidthparameterized complexitycaterpillarsW-hierarchyweighted path emulation

Mathematics Subject Classification ID

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

Related Items

From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability

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