The Bandwidth of Caterpillars with Hairs of Length 1 and 2
From MaRDI portal
Publication:3956996
DOI10.1137/0602041zbMath0494.05059OpenAlexW2073986944MaRDI QIDQ3956996
Jerzy Zak, G. W. Peck, Maciej M. Sysło, Susan F. Assmann
Publication date: 1981
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0602041
Related Items (36)
The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete ⋮ Bandwidth of chain graphs ⋮ Finding the minimum bandwidth of an interval graph ⋮ 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 ⋮ Graph bandwidth of weighted caterpillars ⋮ Restrictions of minimum spanner problems ⋮ Unnamed Item ⋮ Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation} ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Graph layout problems ⋮ Hardness results for approximating the bandwidth ⋮ Approximating the bandwidth for asteroidal triple-free graphs ⋮ Bandwidth of the composition of two graphs. ⋮ Bandwidth and profile minimization ⋮ Bandwidth of trees of diameter at most 4 ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Bandwidth on AT-free graphs ⋮ A note on maximum differential coloring of planar graphs ⋮ Bandwidth of theta graphs with short paths ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete ⋮ An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion ⋮ Bandwidth and topological bandwidth of graphs with few \(P_4\)'s ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion ⋮ Bounds on mincut for Cayley graphs over Abelian groups ⋮ 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 ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Bandwidth of bipartite permutation graphs in polynomial time ⋮ Bandwidth and density for block graphs ⋮ On the bandwidth of the Kneser graph
Cites Work
This page was built for publication: The Bandwidth of Caterpillars with Hairs of Length 1 and 2
