Journal
DISCRETE APPLIED MATHEMATICS
Volume 136, Issue 2-3, Pages 173-182Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0166-218X(03)00439-6
Keywords
product graph; sparsest cut; concurrent flow; bottleneck graph
Categories
Ask authors/readers for more resources
A cut [S,(S) over bar] is a sparsest cut of a graph G if its cut value \S\\(S) over bar \/\[S,(S) over bar] 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 x H are studied. First, a flow in G x H is constructed using optimal flows in G and H, and proven to be optimal. Secondly, two cuts are constructed in G x H using sparsest cuts of G and H. It is shown that one of these cuts is a sparsest cut of G x H. As a consequence, we can prove that G x H is (not) a bottleneck graph if both G and H are (not) bottleneck graphs. (C) 2003 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available