Linear time algorithms for finding sparsest cuts in various graph classes

Share/Save/Bookmark

Bonsma, Paul S. (2007) Linear time algorithms for finding sparsest cuts in various graph classes. Electronic Notes in Discrete Mathematics, 28 . pp. 265-272. ISSN 1571-0653

[img] PDF
Restricted to UT campus only
: Request a copy
237kB
Abstract:[S, S] denotes the set of edges with exactly one end vertex in S. The density of
an edge cut [S, S] is |[S, S]|/(|S||S|). 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.
Item Type:Article
Additional information:6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, DIMATIA Center, Charles University, Prague, July 10-16, 2006
Copyright:© 2007 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/78562
Official URL:http://dx.doi.org/10.1016/j.endm.2007.01.039
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page