Bandwidth and probabilistic complexity
Jonathan Turner · 1982
We study the probabilistic performance of heuristic algorithms for the NP-complete bandwidth minimization problem. Let G = (V,E) be a graph with V = {1,...,n}. Define the bandwidth of G by (DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI) where (tau) ranges over all permutations on V. Let A be a bandwidth minimization algorithm and let A(G) denote the bandwidth of the layout produced by A on the graph G. We say that A is a level algorithm if for all graphs G = (V,E) the layout (tau) produced by A on G satisfies^ (FOR ALL)u,v (ELEM) V d((tau)('-1)(1),u) < d((tau)('-1)(1),v) (IMPLIES) (tau)(u) < (tau)(v)^ The level algorithms were first introduced by Cuthill and McKee and have proved quite successful in practice although it is easy to construct examples that cause them to perform poorly. Consequently worst-case analysis provides no insight into the practical success of these algorithms. In this thesis we use probabilistic analysis in order to gain an understanding of these algorithms and to help us design better algorithms. Let B(,n)('(psi)) = (U,F) be the graph defined by U = {1,...,n}, F = {{u,v}(VBAR)u,v (ELEM) U (WEDGE)(VBAR)u-v(VBAR) (LESSTHEQ) (psi)}, and let G be a random spanning subgraph of B(,n)('(psi)) in which the vertices have been randomly relabelled. We show that if A is a level algorithm and lnn = o((psi)) then A(G) (LESSTHEQ) 3(1 + (epsilon))(phi)(G) almost always holds, where (epsilon) is any positive constant. We also introduce a class of algorithms called the modified level algorithms and show that if A' is a modified level algorithm and lnn = o((psi)) then A'(G) < 2(1 + (epsilon))(phi)(G) almost always holds. A particular level algorithm MLA1 is analyzed and we show that when lnn = o((psi)) and (psi) < n/4, MLA1(G) < (1 + (epsilon))(phi)(G). We also study several other properties of random subgraphs of B(,n)('(psi)).