In graph theory, the graph bandwidth problem is to label the vertices of a graph with distinct integers so that the quantity
max\{|f(vi)-f(vj)|:vivj\inE\}
The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights and the cost function to be minimized is
max\{wij|f(vi)-f(vj)|:vivj\inE\}
In terms of matrices, the (unweighted) graph bandwidth is the minimal bandwidth of a symmetric matrix which is an adjacency matrix of the graph.The bandwidth may also be defined as one less than the maximum clique size in a proper interval supergraph of the given graph, chosen to minimize its clique size .
For fixed
k
i
Ik(i):=[i,i+k+1)
Gk(n)
Ik(1),Ik(2),...Ik(n)
k
L1,L2,...Lk+1
Therefore, one see the relation to the pathwidth. Pathwidth restricted graphs are minor closed butthe set of subgraphs of cyclically interval graphs are not. This follows from the fact, that thrinkingdegree 2 vertices may increase the bandwidth.
Alternate adding vertices on edges can decrease the bandwidth. Hint: The last problem is known astopologic bandwidth. An other graph measure related through the bandwidth is thebisection bandwidth.
For several families of graphs, the bandwidth
\varphi(G)
The bandwidth of a path graph Pn on n vertices is 1, and for a complete graph Km we have
\varphi(Kn)=n-1
\varphi(Km,n)=\lfloor(m-1)/2\rfloor+n
m\gen\ge1,
Sk=Kk,1
\varphi(Sk)=\lfloor(k-1)/2\rfloor+1
Qn
2n
\varphi(Qn)=\sum
| n-1 | |
| m=0 |
\binom{m}{\lfloorm/2\rfloor}.
Pm x Pn
m
n
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,
\varphi(G)\ge\chi(G)-1;
letting diam(G) denote the diameter of G, the following inequalities hold:
\lceil(n-1)/\operatorname{diam}(G)\rceil\le\varphi(G)\len-\operatorname{diam}(G),
where
n
G
If a graph G has bandwidth k, then its pathwidth is at most k, and its tree-depth is at most k log(n/k) . In contrast, as noted in the previous section, the star graph Sk, a structurally very simple example of a tree, has comparatively large bandwidth. Observe that the pathwidth of Sk is 1, and its tree-depth is 2.
Some graph families of bounded degree have sublinear bandwidth: proved that if T is a tree of maximum degree at most ∆, then
\varphi(T)\le
| 5n | |
| log\Deltan |
.
More generally, for planar graphs of bounded maximum degree at most ∆, a similar bound holds (cf.):
\varphi(G)\le
| 20n | |
| log\Deltan |
.
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.[3] Regarding the existence of efficientapproximation algorithms, it is known that the bandwidth is NP-hard to approximate within any constant, and this even holds when the input graphs are restricted to caterpillar trees with maximum hair length 2 .For the case of dense graphs, a 3-approximation algorithm was designed by .On the other hand, a number of polynomially-solvable special cases are known.[4] 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.[5]
The interest in this problem comes from some application areas.
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 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 single row with the goal of minimizing the maximal propagation delay (which is assumed to be proportional to wire length).