Galaxy cutsets in graphs |
| |
Authors: | Nicolas Sonnerat Adrian Vetta |
| |
Affiliation: | 1.Department of Mathematics and Statistics,McGill University,Montreal,Canada;2.Department of Mathematics and Statistics, and School of Computer Science,McGill University,Montreal,Canada |
| |
Abstract: | Given a network G=(V,E), we say that a subset of vertices S⊆V has radius r if it is spanned by a tree of depth at most r. We are interested in determining whether G has a cutset that can be written as the union of k sets of radius r. This generalizes the notion of k-vertex connectivity, since in the special case r=0, a set spanned by a tree of depth at most r is a single vertex. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|