On Small Universal Data Structures and Related Combinatorial Problems.

Abstract

A universal graph for a class of graphs T is a graph G such that every graph in T can be embedded in G with worst-case (average case) loss of proximity bounded by a fixed constant. A universal graph can be interpreted as a universal data structure. Upper and lower bounds are derived for a variety of restrictions on T and G. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1978
Accession Number
ADA062494

Entities

People

  • Richard A. Demillo
  • Richard J. Lipton
  • Stanley Eisenstat

Organizations

  • Georgia Tech

Tags

DTIC Thesaurus Topics

  • Circuit Boards
  • Combinatorial Analysis
  • Computer Science
  • Computers
  • Construction
  • Embedding
  • Graph Theory
  • Mathematics
  • Military Research
  • Numbers
  • Polynomials
  • Real Numbers
  • Schools
  • Theoretical Computer Science
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Computational Linguistics