Compact Representation of the Separating k-sets of a Graph.

Abstract

We present an O(n) space representation for the separating k-sets of an undirected k-connected graph G for fixed k, where n is the cardinality of the vertex set of G. Namely, the total space used by the representation is O(k-squared times n). We also improve the upper bound on the number of separating k-sets of G to O(2 to the kth times(n-squared over k), which has a matching lower bound.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1988
Accession Number
ADA189650

Entities

People

  • Arkady Kanevsky

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Buildings And Structures
  • Classification
  • Computer Science
  • Continents
  • Geographic Regions
  • Illinois
  • Information Processing
  • New York
  • North America
  • Observation
  • Research Facilities
  • Security
  • Semiconductors
  • Two Dimensional
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space