Graph bandwidth: Difference between revisions

Revision as of 12:45, 12 February 2016

Latest revision as of 17:50, 2 July 2025

(17 intermediate revisions by 12 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.

Line 46 ⟶ 67:

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">

Line 64 ⟶ 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 | pmidissue = 5 | pmcarxiv = 0910.3014 }}

*{{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 }}

*{{citation

| last = Chung

| first = Fan R. K.

| author-link =Fan Chung

| last2 =

| first2 =

| author2-link =

| year = 1988

| 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 book

| last = Garey

| first = M.R.

| authorlinkauthor-link = Michael Garey

|author2=Johnson, D.S. |authorlink2author-link2=David S. Johnson

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

| year = 1979

Line 119 ⟶ 125:

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

| year = 2012

| authorlast = Gruber, | first = Hermann

| journal = Journal of Combinatorics

| pages = 669–682

Line 125 ⟶ 131:

| issue = 4

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

| arxiv = 1012.1344

}}

*{{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