Determining the Stability Number of a Graph.

Abstract

Certain rules for deriving upper bounds on the stability number of a graph are formalized. The resulting system is powerful enough to (1) encompass the algorithms of Tarjan's type and (2) provide very short proofs on graphs for which the stability number equals the clique-covering number. However, the main result shows that for almost all graphs with a (sufficiently large) linear number of edges, proofs within the system must have at least exponential length.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1976
Accession Number
ADA038864

Entities

People

  • V. Chavatal

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Inequalities
  • Mathematics
  • Military Research
  • New York
  • Numbers
  • Probability
  • Real Numbers
  • Sampling
  • Sequences
  • Theorems
  • Trees (Data Structures)
  • Unmanned Vehicles

Fields of Study

  • Mathematics

Readers

  • Control Systems Engineering.
  • Graph Algorithms and Convex Optimization.