Graph bandwidth: Difference between revisions

Revision as of 11:05, 23 May 2021

Latest revision as of 17:50, 2 July 2025

(8 intermediate revisions by 7 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 67 ⟶ 88:

==See also==

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

==References==

Line 89 ⟶ 110:

| 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