Loading...
Please wait, while we are loading the content...
Similar Documents
Maximum edge disjoint paths and minimum unweighted multicuts in grid graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bentz, Cédric Costa, Marie-Christine Roupin, Frédéric |
| Copyright Year | 2005 |
| Abstract | In this paper, we solve in polynomial time the maximum edge disjoint paths problem and the related minimum unweighted multicut problem in grid graphs. Let G = (V,E) be an undirected rectilinear grid and let L be a list of K pairs (source sk, sink tk) of terminal vertices of G. Each pair (sk, tk) defines a net. We assume that sources are on the upper horizontal line, sinks are on the lower horizontal line and all the terminals are distinct. The maximum edge disjoint paths problem (MaxEDP) consists in maximizing the number of nets linked by edge disjoint paths. The related minimum multicut problem is to find a minimum set of edges whose removal separates each pair (sk, tk) in an augmented grid (i.e. where each terminal vertex is linked to the graph by a unique edge, e.g. [7]). There exists a duality relationship between the continuous relaxations of linear formulations of these two problems. That implies the cut condition : the number of edge disjoint paths is at most the value of any multicut. Both problems are known to be NP-hard in unrestricted graphs [1], and even in planar graphs ([4], [6]). MaxEDP defined in grids with terminals set at any vertices is also NP-hard [5]. A. Frank gives in ([2], [3]) necessary and sufficient conditions for the existence of K edge disjoint paths when the terminals lay on the upper and lower lines of the grid : there exist K edge disjoint paths if and only if the density is at most the number of horizontal lines and some specific vertices are not terminal vertices. Recall that the density (or the congestion) of a |
| Starting Page | 85 |
| Ending Page | 85 |
| Page Count | 1 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://163.173.228.40/fichiers/RC846.pdf |
| Alternate Webpage(s) | http://cedric.cnam.fr/PUBLIS/RC846.pdf |
| Alternate Webpage(s) | http://cedric.cnam.fr/fichiers/RC846.pdf |
| Alternate Webpage(s) | https://cedric.cnam.fr/fichiers/RC846.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
