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