### 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.

Original language | Undefined |
---|---|

Pages (from-to) | 265-272 |

Journal | Electronic notes in discrete mathematics |

Volume | 28 |

DOIs | |

Publication status | Published - 2007 |

### Keywords

- IR-78562
- graph class
- Sparsest cut
- linear time
- minimum ratio cut

## Cite this

Bonsma, P. S. (2007). Linear time algorithms for finding sparsest cuts in various graph classes.

*Electronic notes in discrete mathematics*,*28*, 265-272. https://doi.org/10.1016/j.endm.2007.01.039