Bandwidth and density for block graphs

DOI10.1016/S0012-365X(98)00009-0zbMath0957.05097arXivmath/9802025MaRDI QIDQ1584358

Le Tu Quoc Hung, Douglas B. West, Margaret L. Weaver, Maciej M. Sysło

Publication date: 2 November 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

labelingbandwidthdensitycliqueblock graphscaterpillars

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (9)

The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete ⋮ Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation} ⋮ Bandwidth of the composition of two graphs. ⋮ On the computation of edit distance functions ⋮ The spider poset is Macaulay ⋮ Optimal vertex ranking of block graphs ⋮ On the dominator coloring in proper interval graphs and block graphs ⋮ VLSI layout of Benes networks ⋮ Block-indifference graphs: characterization, structural and spectral properties

Cites Work

• On minimizing width in linear layouts
• Tolerance graphs
• The NP-completeness of the bandwidth minimization problem
• Bandwidth of the complete \(k\)-ary tree
• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Computing the Bandwidth of Interval Graphs
• A Characterization of Block-Graphs
• The bandwidth problem for graphs and matrices—a survey
• The Bandwidth Problem: critical Subgraphs and the Solution for Caterpillars
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• Complexity Results for Bandwidth Minimization
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Bandwidth and density for block graphs