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. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/S0166-218X(03)00439-6 | Discrete Applied Mathematics |
Keywords | Field | DocType |
cartesian product,upper bound | Cut,Discrete mathematics,Bottleneck,Combinatorics,Vertex (geometry),Upper and lower bounds,Cartesian product,Minimum cut,Graph product,Mathematics,Maximum cut | Journal |
Volume | Issue | ISSN |
136 | 2-3 | 0166-218X |
Citations | PageRank | References |
5 | 0.50 | 5 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paul Bonsma | 1 | 287 | 20.46 |