Graph bandwidth: Difference between revisions

Revision as of 23:39, 8 March 2014

Latest revision as of 17:50, 2 July 2025

(35 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Node labeling problem in graph theory}}

In [[graph theory]], the '''graph bandwidth problem''' is to label the ''n'' vertices ''v_i'' of a graph ''G'' with distinct integers ''f''(''v_i'') so that the quantity <math>\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math> is minimized (''E'' is the edge set of ''G'').<ref>{{harv|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

In [[graph theory]], the '''graph bandwidth problem''' is to label the ''{{mvar|n''}} [[Vertex (graph theory)|vertices]] ''{{mvar|v<{{sub>|i</sub>''}}}} of a [[Graph (discrete mathematics)|graph]] ''{{mvar|G''}} with distinct integers[[integer]]s ''{{tmath|f''(''v_i''v_i)}} so that the quantity <math>\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math> is minimized (''{{mvar|E''}} is the edge set of ''{{mvar|G''}}).<ref>{{harv|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

The problem may be visualized as placing the vertices of a graph at distinct integer points along the ''x''-axis so that the length of the longest edge is minimized. Such placement is called '''linear graph arrangement''', '''linear graph layout''' or '''linear graph placement'''.<ref name=feige/>

The '''weighted graph bandwidth problem''' is a [[generalization]] wherein the edges are assigned [[Graph (discrete mathematics)#Weighted_graph|weights]] ''{{mvar|w<{{sub>|ij</sub>''}}}} and the [[Loss function|cost function]] to be minimized is <math>\max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math>.

In terms of matrices, the (unweighted) graph bandwidth is the minimal [[bandwidth (matrix theory)|bandwidth]] of thea [[symmetric matrix]] which is thean [[adjacency matrix]] of the graph.

The bandwidth may also be defined as one less than the [[maximum clique]] size in a [[proper interval graph|proper interval]] supergraph of the given graph, chosen to minimize its clique size {{harv|Kaplan|Shamir|1996}}.

==Cyclically interval graphs==

For fixed <math>k</math> define for every <math>i</math> the set

<math>I_k(i) := [i, i+k+1)</math>. <math>G_k(n)</math> is the corresponding interval graph formed from

the intervals <math>I_k(1), I_k(2), ... I_k(n)</math>. These are '''exactly''' the proper interval

graphs of graphs having bandwidth <math>k</math>. These graphs are called

'''cyclically interval graphs''' because the intervals can be assigned to layers

<math>L_1, L_2, ... L_{k+1}</math> in cyclical order, such that the intervals of a layer don't

intersect.

Therefore, one can see the relation to the [[pathwidth]]. Pathwidth restricted graphs are minor closed but

the set of subgraphs of cyclically interval graphs are not. This follows from the fact that thrinking

degree 2 vertices may increase the bandwidth.

Alternate adding vertices on edges can decrease the bandwidth. This is known as

'''topologic bandwidth'''. Another graph measure related through the bandwidth is the

[[bisection bandwidth]].

==Bandwidth formulas for some graphs==

For several families of graphs, the bandwidth <math>\varphi(G)</math> is given by an explicit formula.

The bandwidth of a [[path graph]] ''P''<mathsub>P_n''n''</mathsub> on ''n'' vertices is <math>&nbsp;1</math>, and for a complete graph ''K''<mathsub>K_m''m''</mathsub> we have <math>\varphi(K_n)=n-1</math>. For the [[complete bipartite graph]] ''K''<mathsub>K_{''m'',''n},''</mathsub>,

:<math>\varphi(K_{m,n}) = \lfloor (m-1)/2\rfloor+n</math>, assuming <math>m \ge n\ge 1</math>,

:<math>\varphi(K_{m,n}) = \lfloor (m-1)/2\rfloor+n</math>, assuming <math>m \ge n\ge 1,</math>

which was proved by Chvátal.<ref>A remark on a problem of Harary. V. Chvátal, ''Czechoslovak Mathematical Journal'' '''20'''(1):109&ndash;111, 1970. [http://dml.cz/dmlcz/100949 http://dml.cz/dmlcz/100949]</ref> As a special case of this formula, the [[star graph]] <math>S_k = K_{k,1}</math> on ''k''&nbsp;+&nbsp;1 vertices has bandwidth <math>\varphi(S_{k}) = \lfloor (k-1)/2\rfloor+1</math>.

For the [[hypercube graph]] <math>Q_n</math> on <math>2^n</math> vertices the bandwidth was determined by {{harvtxt|Harper|1966}} to be

:<math>\varphi(Q_n)=\sum_{m=0}^{n-1} \binom{m}{\lfloor m/2\rfloor}.</math>

Chvatálová showed<ref>Optimal Labelling of a product of two paths. J. Chvatálová, ''Discrete Mathematics'' '''11''', 249&ndash;253, 1975.</ref> that the bandwidth of the <math>(''m \''&nbsp;&times ;&nbsp;''n)</math>'' [[lattice graph|square grid graph]] <math>P_m \times P_n</math>, that is, the [[Cartesian product of graphs|Cartesian product]] of two path graphs on <math>m</math> and <math>n</math> vertices, is equal to <math>\&nbsp;min\{''m'',''n\''}</math>.

==Bounds==

The bandwidth of a graph can be bounded in terms of various other graph parameters. For instance, letting χ(''G'') denote the [[chromatic number]] of ''G'',

:φ(''G'') ≥ χ(''G'')-1;

: <math> \varphi(G) \le 20n /ge \log_\Deltachi(G) - n1; </math>.

letting diam(''G'') denote the [[diameter (graph theory)|diameter]] of ''G'', the following inequalities hold:<ref>{{harvnb|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

:<math>\lceil (n-1)/\mathrmoperatorname{diam}(G) \rceil \le \varphi(G) \le n - \mathrmoperatorname{diam}(G),</math>,

where <math>n</math> is the number of vertices in <math>G</math>.

If a graph <math>''G</math>'' has bandwidth <math>''k</math>'', then its [[pathwidth]] is at most <math>''k</math>'' {{harv|Kaplan|Shamir|1996}}, and its [[tree-depth]] is at most <math>''k\''&nbsp;log(''n''/''k'')</math> {{harv|Gruber|2012}}. In contrast, as noted in the previous section, the star graph ''S''<mathsub>S_k''k''</mathsub>, a structurally very simple example of a [[tree (graph theory)|tree]], has comparatively large bandwidth. Observe that the [[pathwidth]] of ''S''_''k'' is&nbsp;1, and its tree-depth is&nbsp;2.

very simple example of a [[tree (graph theory)|tree]], has comparatively large bandwidth. Observe that the [[pathwidth]] of <math>S_k</math> is 1, and its tree-depth is 2.

Some graph families of bounded degree have sublinear bandwidth: {{harvtxt|Chung|1988}} proved that if ''T'' is a tree of maximum degree at most ''∆'', then

:<math>\varphi(T) \le \frac{5n / }{\log_\Delta n}. </math>.

Some graph families of bounded degree have sublinear bandwidth: {{harvtxt|Chung|1988}} proved that if ''T'' is a tree of maximum degree at most ''∆'', then

:<math>\varphi(T) \le 5n / \log_\Delta n</math>.

More generally, for [[planar graph]]s of bounded maximum degree at most ''∆'', a similar bound holds (cf. {{harvnb|Böttcher|Pruessmann|Taraz|Würfl|2010}}):

:<math>\varphi(G) \le 20n / \log_\Delta n </math>.

:<math>\varphi(G) \le \frac{20n}{\log_\Delta n}.</math>

==Computing the bandwidth==

Both the unweighted and weighted versions are special cases of the [[quadratic bottleneck assignment problem]].

The bandwidth problem is [[NP-hard]], even for some special cases.<ref>Garey–Johnson: GT40</ref> Regarding the existence of efficient

[[approximation algorithm]]s, it is known that the bandwidth is [[hardness of approximation|NP-hard to approximate]] within any constant, and this even holds when the input graphs are restricted to [[caterpillar tree]]s with maximum hair length 2 {{harv|Dubey|Feige|Unger|2010}}.
For the case of dense graphs, a 3-approximation algorithm was designed by {{harvtxt|Karpinski|Wirtgen|Zelikovsky|1997}}.
On the other hand, a number of polynomially-solvable special cases are known.<ref name=feige>"Coping with the NP-Hardness of the Graph Bandwidth Problem", Uriel Feige, ''[[Lecture Notes in Computer Science]]'', Volume 1851, 2000, pp. 129-145, {{doi|10.1007/3-540-44985-X_2}}</ref> A [[heuristic]] algorithm for obtaining linear graph layouts of low bandwidth is the [[Cuthill–McKee algorithm]]. Fast multilevel algorithm for graph bandwidth computation was proposed in.<ref name="multilevellinord">

{{cite journal

| author = Ilya Safro and Dorit Ron and Achi Brandt

Line 45 ⟶ 77:

| pages = 1.4–1.20

| volume = 13

| doi=10.1145/1412228.1412232

}}</ref>

Line 52 ⟶ 85:

One area is [[sparse matrix]]/[[band matrix]] handling, and general algorithms from this area, such as [[Cuthill–McKee algorithm]], may be applied to find approximate solutions for the graph bandwidth problem.

Another application ___domain is in [[electronic design automation]]. In [[standard cell]] design methodology, typically standard cells have the same height, and their [[placement (EDA)|placement]] is arranged in a number of rows. In this context, graph bandwidth problem models the problem of placement of a set of standard cells in a singesingle row with the goal of minimizing the maximal [[propagation delay]] (which is assumed to be proportional to wire length).

==See also==

*[[PathwidthCutwidth]], aand [[pathwidth]], different NP-complete optimization problemproblems involving linear layouts of graphs.

==References==

{{reflist}}

*{{Cite journal | last1 = Böttcher | first1 = J. | last2 = Pruessmann | first2 = K. P. | last3 = Taraz | first3 = A. | last4 = Würfl | first4 = A. | title = Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs | doi = 10.1016/j.ejc.2009.10.010 | journal = European Journal of Combinatorics | volume = 31 | pages = 1217–1227 | year = 2010 | issue = 5 | arxiv = 0910.3014 }}

*{{cite doi|10.1016/j.ejc.2009.10.010}}

*{{Cite journal | last1 = Chinn | first1 = P. Z. |author1-link=Phyllis Chinn| last2 = Chvátalová | first2 = J. | last3 = Dewdney | first3 = A. K. |author3-link=Alexander Dewdney| last4 = Gibbs | first4 = N. E. | title = The bandwidth problem for graphs and matrices—a survey | journal = Journal of Graph Theory | volume = 6 | pages = 223–254| year = 1982 | issue = 3 | doi = 10.1002/jgt.3190060302 }}

*{{cite doi|10.1002/jgt.3190060302}}

*{{citation

| last = Chung

| first = Fan R. K.

| author-link =Fan Chung

| last2 =

| first2 =

| author2-link =

| year = 1988

| date =

| publication-date =

| contribution = Labelings of Graphs

| editor2editor-last = Beineke

| contribution-url =

| editor-lastfirst = Lowell W.

| editoreditor2-firstlast = Wilson

| editoreditor2-linkfirst = Robin J.

| editor2-last = Beineke

| editor2-first = Lowell W.

| editor2-link =

| title = Selected Topics in Graph Theory

| edition =

| series =

| place =

| publication-place =

| publisher = Academic Press

| volume =

| pages = 151–168

| id =

| isbn = 978-0-12-086203-0

| doi =

| oclc =

| url = http://www.math.ucsd.edu/~fan/mypaps/fanpap/86log.PDF

}}

*{{Cite journal | last1 = Dubey | first1 = C. | last2 = Feige | first2 = U. | last3 = Unger | first3 = W. | title = Hardness results for approximating the bandwidth | journal = Journal of Computer and System Sciences | volume = 77 | pages = 62–90| year = 2010 | doi = 10.1016/j.jcss.2010.06.006 | doi-access = free }}

*{{cite doi|10.1016/j.jcss.2010.06.006}}

* {{cite book

| last = Garey

| first = M.R.

| authorlinkauthor-link = Michael Garey

|author2=Johnson, coauthorsD.S. |author-link2= [[David S. Johnson|Johnson, D.S.]]

| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]

| year = 1979

Line 108 ⟶ 125:

| title = On Balanced Separators, Treewidth, and Cycle Rank

| year = 2012

| authorlast = Gruber, | first = Hermann

| journal = Journal of Combinatorics

| pages = 669–682

| volume = 3

| issue = 4

| doi=10.4310/joc.2012.v3.n4.a5

}}

| arxiv = 1012.1344

*{{cite doi|10.1016/S0021-9800(66)80059-5}}

}}

*{{Cite journal | last1 = Harper | first1 = L. | title = Optimal numberings and isoperimetric problems on graphs | journal = Journal of Combinatorial Theory | volume = 1 | pages = 385–393 | year = 1966 | issue = 3 | doi = 10.1016/S0021-9800(66)80059-5 | doi-access = free }}

*{{Citation

| title = Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques

| year = 1996

| journal = [[SIAM Journal on Computing]]

| pages = 540–561

| volume = 25

| last2issue = 3

| last1 = Kaplan | first1 = Haim

| last2 = Shamir | first2 = Ron }}

| doi=10.1137/s0097539793258143}}

*

*{{Cite journal

| last1 = Karpinski | first1 = Marek

| last2 = Wirtgen | first2 = Jürgen

| last3 = Zelikovsky | first3 = Aleksandr

| title = An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

| journal = Electronic Colloquium on Computational Complexity

| volume = 4 | number = 17

| year = 1997

| url = http://eccc.hpi-web.de/report/1997/017/

}}

==External links==