| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652846 | Electronic Notes in Discrete Mathematics | 2007 | 8 Pages |
Abstract
denotes the set of edges with exactly one end vertex in S. The density of an edge cut is . A sparsest cut is an edge cut with minimum density. We characterize the sparsest cuts for unit interval graphs, complete bipartite graphs and cactus graphs. For all of these classes, the characterizations lead to linear time algorithms to find a sparsest cut.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
