Bounding the bandwidths for graphs
type: Item
instance of: scholarly article
title: Bounding the bandwidths for graphs
zbMATH Open document ID: 0949.68120
DOI: 10.1016/S0304-3975(00)00068-2
published in: Theoretical Computer Science
publication date: 2000-10-26T00:00:00Z
review text: Let \(G,H\) be finite graphs with \(|V(H)|\geqslant|V(G)|\). The bandwidth of \(G\) with respect to \(H\) is defined to be \(B_H(G)=\min_{\pi} \max_{uv\in E(G)} d_H(\pi(u),\pi(v))\), with the minimum taken over all injections \(\pi\) from \(V(G)\) to \(V(H),\) where \(d_{H}(x,y)\) is the distance in \(H\) between two vertices \(x,y \in V(H)\). This number is involved with the VLSI design and optimization, especially when the ``host'' graph \(H\) is a path \(P_{n}\) or a cycle \(C_{n}\) of length \(n=|V(G)|\). In these two cases, \(B_{H}(G)\) is known to be the ordinary bandwidth \(B(G)\) and the cyclic bandwidth \(B_{c}(G),\) respectively, and the corresponding decision problem is NP-complete. So estimations of \(B(G),\) \(B_{c}(G)\) and in general \(B_{H}(G)\) are needed, especially in determining the bandwidths of some specific graphs. We first propose a systematic method for obtaining lower bounds for the bandwidth \(B_{H}(G).\) By using this method, we then get a number of lower bounds for \(B(G)\) and \(B_{c}(G)\) in terms of some distance- and degree-related parameters.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1521898
zbMATH Keywords: bandwidth
zbMATH Keywords: cyclic bandwidth
zbMATH Keywords: VLSI layout
author: Sanming Zhou
MaRDI profile type: Publication
cites work: A framework for solving VLSI graph layout problems
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Q3803160
cites work: A remark on a problem of Harary
cites work: Parallel concepts in graph theory
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Q4294611
cites work: Q4321827
cites work: Q4871643
cites work: Q4347280
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Harper-type lower bounds and the bandwidths of the compositions of graphs
cites work: Interpolation theorems for graphs, hypergraphs and matroids
description: scientific article; zbMATH DE number 1521898