ABSTRACT
We study the probabilistic performance of heuristic algorithms for the NP-complete bandwidth minimization problem. Let (equation) be a graph with (equation). Define the bandwidth of G by (equation) where τ 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 (equation) the layout τ produced by A on G satisfies (equation) The level algorithms were first introduced by Cuthill and McKee [1] and have proved quite successful in practice. However, it is easy to construct examples that cause the level algorithms to perform poorly. Consequently worst-case analysis provides no insight to their practical success. In this paper we use probabilistic analysis in order to gain an understanding of these algorithms and to help us design better algorithms.
Let (equation) be the graph defined by (equation) and let G be a random spanning subgraph of Bn↓ in which the vertices have been randomly re-labelled. We show that if A, is a level algorithm and (equation) then (equation) almost always holds, where ε 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 (equation) then (equation) almost always holds. A particular modified level algorithm MLA1 is analyzed and we show that when (equation). We also study several other properties of random subgraphs of Bn↓.
- 1.Cuthill, E., J. McKee. "Reducing the Bandwidth of Sparse Symmetric Matrices" In ACM National Conference Proceedings 24, 157-172, 1969. Google ScholarDigital Library
- 2.Papadimitriou, C. H. "The NP-Completeness of the Bandwidth Minimization Problem" In Computing 16, 1976, 263-270.Google ScholarCross Ref
- 3.Garey, M. R., R. L. Graham, D. S. Johnson, D. E. Knuth. "Complexity Results for Bandwidth Minimization" In SIAM Journal of Applied Mathematics 34, 5/78, 477-495.Google ScholarDigital Library
- 4.Saxe, James B. "Dynamic Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time". Carnegie-Mellon University Technical Report, 1980.Google Scholar
- 5.Monien, B., I. H. Sudborough. "Bandwidth Problems in Graphs." In Proceedings 18th Annual Allerton Conference on Communication, Control, and Computing, 650-659, 1980.Google Scholar
- 6.Turner, Jonathan. "Bandwidth and Probabilistic Complexity" Ph.D. Thesis, Northwestern University, June 1982. Google ScholarDigital Library
- 7.Erdös, P., A. Renyi. "On Random Graphs I.". In Publicationes Mathematicae, 1959, 290-297.Google Scholar
- 8.Chvatal, V. "A Remark on a Problem of Harary". In Czechoslovak Math Journal 20, 95, 1970.Google Scholar
Index Terms
Probabilistic analysis of bandwidth minimization algorithms
Recommendations
Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
Let G be a graph in which each vertex v has a positive integer weight b ( v ) and each edge ( v , w ) has a nonnegative integer weight b ( v , w ) . A bandwidth consecutive multicoloring, simply called a b-coloring of G, assigns each vertex v a ...
Analysis for parareal algorithms applied to Hamiltonian differential equations
AbstractLong-time integrations are an important issue in the numerical solution of Hamiltonian systems. They are time consuming and it is natural to consider the use of parallel architectures for reasons of efficiency. In this context the ...
Edge-Bandwidth of Graphs
The edge-bandwidth of a graph is the minimum, over all labelings of the edges with distinct integers, of the maximum difference between labels of two incident edges. We prove that edge-bandwidth is at least as large as bandwidth for every graph, with ...
Comments