
Accession Number : ADA189650
Title : Compact Representation of the Separating ksets 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 ksets of an undirected kconnected 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(ksquared times n). We also improve the upper bound on the number of separating ksets of G to O(2 to the kth times(nsquared over k), which has a matching lower bound.
Descriptors : *GRAPHS, MATCHING, SET THEORY
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE