Bounding the bandwidths for graphs

DOI10.1016/S0304-3975(00)00068-2MaRDI QIDQ1583541zbMATH OpenFDO

Authors Sanming Zhou

Publication date 26 October 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00068-2

zbMATH Keywords

bandwidth cyclic bandwidth VLSI layout

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

Cites work

Cited in

(30)

This page was built for publication: Bounding the bandwidths for graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583541)