Report

Bandwidth/Cutwidth Matt Huddleston CS 594: Graph Theory Thursday, March 27, 14 Definitions • When the vertices of a graph G are numbered with distinct integers, the dilation is the maximum difference between integers assigned to adjacent vertices. More Definitions • The bandwidth B(G) of a graph G is the minimum dilation of a numbering of G. – Equivalently, it is the minimum matrix bandwidth among all possible adjacency matrices of graphs isomorphic to G. • A bandwidth numbering of G is a proper numbering f such that B(G) = Bf(G) – A proper numbering that achieves B(G) (West, 2001, p. 390) More Definitions • The cutwidth of G = (V, E) is defined to be the maximum number of edges from E that must be cut between consecutive vertices in any linear layout of V. Cutwidth Example (Graph: Martí, Pantrigo, Duarte, and Pardo. [2013]) Example The Bandwidth Minimization Problem (BMP) • Finding the minimum bandwidth is NPhard (Papadimitriou [1976]) – Even for simple graphs • NP-Hard for trees • Also, NP-Hard for trees that are caterpillars with hair length 3. (Garey-Graham-JohnsonKnuth[1978]) • O(n log n) when hair length is 1 or 2 Example BMP History • Originated in the late 50’s and early 60’s in many ways – Structural engineers tried to analyze steel frameworks by computer manipulation of thier ‘Structural’ matrices. – at Jet Propulsion Laboratory in Pasadena. harper and hales were trying to construct the codes to minimize the max and avg absolute errors. (Shikare and Waphare [2004]) More BMP History • In the 60’s Korfhage began work on the BMP • Shortly after Harary made the BMP public at a conference in Prague • Problem received notable attention until Papadimitriou found that the BMP for graphs and matrices is NP-Complete (Shikare and Waphare [2004]) The Cutwidth Minimization Problem (CMP) • Find a linear layout of a graph so the maximum linear cut is minimized. • In 1977 Gavril showed that this is a NPHard problem BMP & CMP • Associated with many optimization problems in circuit layout • BMP – Standard cell design – Network addressing • CMP – – – – VLSI design network communications automatic graph drawings information retrieval Examples/Facts • Bandwidth of an arbitrary tree cannot be determined • Ando, Kaneko and Gervacio gave the following bound. – If T is a tree with k pendent vertices, then B(T) ≤ |k/2| (ceiling on k/2) Examples/Facts • The bandwidth of the singleton graph is not defined, but the conventions bw(K1)=0 or bw(K1)=1 are sometimes adopted. (Miller [1988]) • If H is a subgraph of G, then B(H) ≤ B(G) – An optimal labeling of G is also a labeling of H. Examples • B(Pn ) = ? • A nontrivial graph has bandwidth 1 – Iff it can be ordered so that it’s nonconsecutive vertices are adjacent – Making all components paths Examples • B(Cn ) = ? – Cn has n edges – there are only n-1 consecutive pairs among the numbers 0,..,n-1. – Some adjacent pair of vertices of Cn must be labeled with non consecutive integers – B(Cn) = 2 Example 4 2 (Gross, Yellen []) Bandwidth Special Cases (Weisstein) Examples • Cutwidth approximation in linear time – Bounded width – Finite (unknown) list of obstruction tests – Most fundamental test is to determine whether K4 is immersed in the graph. • K4 obstructs cutwidth 3 • Any arrangement of its vertices on a line (Booth, Govindan, Langston, and Ramachandramurthi [1992]) Examples K4 immersion (Booth, Govindan, Langston, and Ramachandramurthi [1992]) Bounds on the Bandwidth • Graphs that have similar values of a certain parameter may have bandwidth arbitrarily far apart. – This shows that bandwidth is an independent parameter in its own right. – Bounds can still be important in certain graphs. Bounds on Bandwidth • For any graph G, – B(G) ≥ [Δ(G)/2] • Attained when G=K1,n – B(G) ≥ χ(G)-1 • Attained when G=Kn – B(G) ≥ n-1/2(2-[(2n-1)2-8e]1/2) (Dewdney) • For this n and e denote the number of edges and vertices in G, respectively. • Attained when G=Kn More Bounds on Bandwidth • Local density bound (Chung [1988]) • Every numbering of G contains a subgraph of G • On every subgraph H – Two numbers differing by at least n(H) – 1 are used – Some edge on a path between corresponding vertices has dilation at least n(H) – 1 divided by distance between More Bounds on Bandwidth B(G) > maxk min|S|=k |δS| • For all k, some set S must be the first k vertices in the optimal numbering of G • Bandwidth must be at least |δS| – Vertex among δS that has the least label has an edge dilation at least |δS| to its neighborhood above S. (Harper [1966]) Other Applications • Matrix handling – The Cuthill–McKee algorithm • Algorithm to permute a symmetric matrix with small bandwidth – The reverse Cuthill–McKee algorithm (Alan George) • same algorithm but with the resulting index numbers reversed. • generally results in less fill-in than the CM ordering Cuthill-McKee Cuthill-McKee Ordering Reverse Cuthill-McKee Ordering Examples • Bandwidth Coloring Problem – This problem generalizes the classical vertex coloring problem. • Let G=(V,E) be a graph with a strictly positive integer weight dij associated to each edge (i, j) ∈ E. • A k-coloring c of G labels each vertex i ∈ V with an integer c(i) ∈ {1, 2, ..., k} (called color) in such a way that |c(i) - c(j)| ≥ dij for all (i, j) ∈ E. • The bandwidth coloring problem (BCP) consists of finding a k coloring with the smallest value of k. Other Applications • University of Ottawa published “Generalized Gene Adjacencies, Graph Bandwidth, and Clusters in Yeast Evolution” – Present a “parameterized definition of gene clusters that allows us to control emphasis placed on conserved order within a cluster” – This turns out to be closely related to the bandwidth of a graph Homework 1. What is the bandwidth of the following graph: Homework • 2. Compute the bandwidth of Kn. Homework • 3. What is the bandwidth of the following graph: References • • • • • • • • • Ando, Kiyoshi, Atsusi Kaneko, and Severino Gervacio. "The Bandwidth of a Tree with K Leaves Is at Most." Discrete Mathematics 150.1-3 (1996): 403-06. Print. Beineke, Lowell W., and Robin J. Wilson. Selected Topics in Graph Theory 3. London: Academic, 1988. Print. Booth, H.D.; Govindan, R.; Langston, M.A.; Ramachandramurthi, S., "Cutwidth approximation in linear time," VLSI, 1992., Proceedings of the Second Great Lakes Symposium on , vol., no., pp.70,73, 28-29 Feb 1992 Chung F.R.K., Labellings of graphs. In Selected Topics in Graph Theory, Vol. 3. (ed. L.W. Beinke and R.J. Wilson) Acad. Press (1988), 151-168. Cuthill, E., and J. McKee. Reducing the Bandwidth of Sparse Symmetric Matrices. Ft. Belvoir: Defense Technical Information Center, 1969. Print. Garey, M. R., R. L. Graham, D. S. Johnson, and D. E. Knuth. "Complexity Results for Bandwidth Minimization." SIAM Journal on Applied Mathematics 34.3 (1978): 477. Print. Gavril, F. Some NP-complete problems on graphs. In Proceedings of the 11th conference on information Sciences and Systems, 91-95, 1977. Gross, Jonathan L., and Jay Yellen. Graph Theory and Its Applications. Boca Raton: Chapman & Hall/CRC, 2006. Print. Harper L.J., Optimal numberings and isoperimetric problems on graphs. J. Comb. Th. 1 (1966), 385-393. More References • • • • • • • • Martí, Rafael, Juan J. Pantrigo, Abraham Duarte, and Eduardo G. Pardo. "Branch and Bound for the Cutwidth Minimization Problem." Computers & Operations Research 40.1 (2013): 137-49. Print. Miller, Z. "A Linear Algorithm for Topological Bandwidth with Degree-Three Trees." SIAM J. Comput. 17, 1018-1035, 1988. Qian Zhu; Adam, Z.; Choi, V.; Sankoff, D., "Generalized Gene Adjacencies, Graph Bandwidth, and Clusters in Yeast Evolution," Computational Biology and Bioinformatics, IEEE/ACM Transactions on , vol.6, no.2, pp.213,220, April-June 200 Papadimitriou, Ch. H. "The NP-Completeness of the Bandwidth Minimization Problem." Computing 16.3 (1976): 263-70. Print. R. R. Korfhage, Numberings of the vertices of graphs, Computer Science Department, Technical Report #5, Purdue University, Lafayette, IN (1966) Shikare, M. M., and B. N. Waphare. Combinatorial Optimization. New Delhi: Narosa Pub. House, 2004. Print. Weisstein, Eric W. "Graph Bandwidth." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphBandwidth.html West, Douglas Brent. Introduction to Graph Theory. Upper Saddle River, NJ: Prentice Hall, 2001. Print.