The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete

DOI10.1137/0607057zbMath0624.68059OpenAlexW2022822152MaRDI QIDQ3026359

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-4419

zbMATH Keywords

trees NP completeness bandwidth minimization caterpillars with hairs of length at most three

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (53)

The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete ⋮ Bandwidth of chain graphs ⋮ Bandwidth Minimization: An approximation algorithm for caterpillars ⋮ On semidefinite programming bounds for graph bandwidth ⋮ Faster Exact Bandwidth ⋮ Euclidean Networks with a Backbone and a Limit Theorem for Minimum Spanning Caterpillars ⋮ Approximating the bandwidth of caterpillars ⋮ Graph bandwidth of weighted caterpillars ⋮ Min Cut is NP-complete for edge weighted trees ⋮ Unnamed Item ⋮ Lower bounds for the bandwidth problem ⋮ Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation} ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Embedding ladders and caterpillars into the hypercube ⋮ Hardness results for approximating the bandwidth ⋮ Tangle bases: Revisited ⋮ Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Unnamed Item ⋮ Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs ⋮ Interval degree and bandwidth of a graph ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ Bandwidth and profile minimization ⋮ Bandwidth of trees of diameter at most 4 ⋮ A combinatorial optimization algorithm for solving the branchwidth problem ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Bandwidth on AT-free graphs ⋮ A note on maximum differential coloring of planar graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems ⋮ Cyclic bandwidth with an edge added ⋮ Approximation algorithms for the bandwidth minimization problem for a large class of trees ⋮ Bandwidth of theta graphs with short paths ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Minimal proper interval completions ⋮ Exact and approximate bandwidth ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ Bandwidth of Bipartite Permutation Graphs in Polynomial Time ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ On the proper intervalization of colored caterpillar trees ⋮ Selected papers in honor of Manuel Blum on the occasion of his 60th birthday. Selected papers from the international conference in Theoretical Computer Science, Hong Kong, April 20-24, 1998 ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Bandwidth of bipartite permutation graphs in polynomial time ⋮ A fixed-parameter tractability result for multicommodity demand flow in trees ⋮ Bandwidth and density for block graphs ⋮ Packing of (0, 1)-matrices ⋮ The Proper Interval Colored Graph problem for caterpillar trees ⋮ On the bandwidth of the Kneser graph ⋮ Equitable colorings of bounded treewidth graphs

Cites Work

This page was built for publication: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete