Accession Number : ADA189650

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

Descriptive Note : Technical rept.,

Corporate Author : ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Kanevsky, Arkady

PDF Url : ADA189650

Report Date : Jan 1988

Pagination or Media Count : 31

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.

Descriptors :   *GRAPHS, MATCHING, SET THEORY

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE