The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars

DOI10.1016/S0304-0208(08)72457-5zbMath0494.05058OpenAlexW63379696MaRDI QIDQ3956995

Maciej M. Sysło, Jerzy Zak

Publication date: 1982

Published in: North-Holland Mathematics Studies (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-0208(08)72457-5

zbMATH Keywords

bandwidthvertex-labellingcaterpillarsefficient labelling procedureorder and diameter of subtrees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (05C99)

Related Items

The bandwidth problem and operations on graphs ⋮ Bandwidth Minimization: An approximation algorithm for caterpillars ⋮ Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation} ⋮ Bandwidth of the composition of two graphs. ⋮ Bandwidth of trees of diameter at most 4 ⋮ Two models of two-dimensional bandwidth problems ⋮ On Harpers' Result Concerning the Bandwidths of Graphs ⋮ Bandwidth and density for block graphs