The Diameter of Almost All Bipartite Graphs.

Abstract

The diameter of a graph is of intrinsic interest as one of the most basic and most thoroughly studied parameters of graph theory. It may also be of practical concern because of the close relationship of diameters to the computational complexity of graph-theoretic algorithms based on breadth-first search. Here we consider bipartite graphs on n labelled points in one part and m=m(n) < n labelled points in the other. Of the 2mn such graphs, some are disconnected and the others have diameters ranging from 2m down to 2. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1980
Accession Number
ADA087687

Entities

People

  • D. G. Larman
  • E. M. Wright
  • V. L. Klee

Organizations

  • University of Washington

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Analogs
  • Classification
  • Computational Complexity
  • Computations
  • Diameters
  • Governments
  • Graph Theory
  • Mathematics
  • Military Research
  • Probability
  • Security
  • Sequences
  • United States
  • United States Government

Readers

  • Graph Algorithms and Convex Optimization.