Graph bandwidth: Difference between revisions

Revision as of 15:49, 2 November 2021

Revision as of 22:09, 21 June 2022

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 a [[symmetric matrix]] which is an [[adjacency matrix]] of the graph.