# Sparsest cuts and concurrent flows in product graphs

Bonsma, Paul
(2004)
*Sparsest cuts and concurrent flows in product graphs.*
Discrete Applied Mathematics, 136
(2-3).
pp. 173-182.
ISSN 0166-218X

PDF
Restricted to UT campus only : Request a copy 289kB |

Abstract: | A cut [S.S] is a sparsest cut of a graph G if its cut value [S][S]/[S.S] is maximum (this is the reciprocal of the well-known edge-density of the cut). In the (undirected) uniform concurrent flow problem on G, between every vertex pair of G flow paths with a total flow of 1 have to be established. The objective is to minimize the maximum amount of flow through an edge (edge congestion). The minimum congestion value of the uniform concurrent flow problem on G is an upper bound for the maximum cut value of cuts in G. If both values are equal, G is called a bottleneck graph. The bottleneck properties of cartesian product graphs G×H are studied. First, a flow in G×H is constructed using optimal flows in G and H, and proven to be optimal. Secondly, two cuts are constructed in G×H using sparsest cuts of G and H. It is shown that one of these cuts is a sparsest cut of G×H. As a consequence, we can prove that G×H is (not) a bottleneck graph if both G and H are (not) bottleneck graphs. |

Item Type: | Article |

Copyright: | © 2004 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/72726 |

Official URL: | http://dx.doi.org/10.1016/S0166-218X(03)00439-6 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 219903