skip to main content
10.1145/800061.808778acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free Access

Probabilistic analysis of bandwidth minimization algorithms

Published:01 December 1983Publication History

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↓.

References

  1. 1.Cuthill, E., J. McKee. "Reducing the Bandwidth of Sparse Symmetric Matrices" In ACM National Conference Proceedings 24, 157-172, 1969. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. 2.Papadimitriou, C. H. "The NP-Completeness of the Bandwidth Minimization Problem" In Computing 16, 1976, 263-270.Google ScholarGoogle ScholarCross RefCross Ref
  3. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  4. 4.Saxe, James B. "Dynamic Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time". Carnegie-Mellon University Technical Report, 1980.Google ScholarGoogle Scholar
  5. 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 ScholarGoogle Scholar
  6. 6.Turner, Jonathan. "Bandwidth and Probabilistic Complexity" Ph.D. Thesis, Northwestern University, June 1982. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 7.Erdös, P., A. Renyi. "On Random Graphs I.". In Publicationes Mathematicae, 1959, 290-297.Google ScholarGoogle Scholar
  8. 8.Chvatal, V. "A Remark on a Problem of Harary". In Czechoslovak Math Journal 20, 95, 1970.Google ScholarGoogle Scholar

Index Terms

  1. Probabilistic analysis of bandwidth minimization algorithms

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computing
        December 1983
        487 pages

        Copyright © 1983 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 1 December 1983

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • Article

        Acceptance Rates

        Overall Acceptance Rate1,469of4,586submissions,32%

        Upcoming Conference

        STOC '24
        56th Annual ACM Symposium on Theory of Computing (STOC 2024)
        June 24 - 28, 2024
        Vancouver , BC , Canada

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader