Content deleted Content added
fix reflinks |
grammar |
||
| (16 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<sub>i</sub>'' of a graph ''G'' with distinct integers ''f''(''v<sub>i</sub>'') 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
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]]
In terms of matrices, the (unweighted) graph bandwidth is the minimal [[bandwidth (matrix theory)|bandwidth]] of
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
==See also==
*[[
==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 |
*{{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
| year = 1988
| contribution = Labelings of Graphs
| editor-
|
|
▲ | editor2-last = Beineke
| title = Selected Topics in Graph Theory
| publisher = Academic Press
| pages = 151–168
| isbn = 978-0-12-086203-0
| 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 |
* {{cite book
| last = Garey
| first = M.R.
|
|author2=Johnson, D.S. |
| title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
| year = 1979
Line 116 ⟶ 121:
| ___location = New York
| isbn = 0-7167-1045-5
}}
*{{Citation
Line 127 ⟶ 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 |
*{{Citation
| title = Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques
Line 139 ⟶ 143:
| last1 = Kaplan | first1 = Haim
| last2 = Shamir | first2 = Ron
| doi=10.1137/s0097539793258143}}
*{{Cite journal
Line 150 ⟶ 153:
| year = 1997
| url = http://eccc.hpi-web.de/report/1997/017/
}}
| |||