| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Optimal Solution of the Maximum All Request Path Grooming Problem
Abstract : We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application. The MARPG problem consists in finding the maximum number of connections which can be established in a path of size N, where each arc has a capacity or bandwidth C (grooming factor). We present a greedy algorithm to solve the problem and an explicit formula for the maximum number of requests that can be groomed. In particular, if C = s(s 1)/2 and N > s(s-1), an optimal solution is obtained by taking all the requests of smallest length, that is of length 1 to s. However this is not true in general since anomalies can exist. We give a complete analysis and the exact number of such anomalies.
https://hal.inria.fr/inria-00429167
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Sunday, November 1, 2009 - 1:43:37 PM
Last modification on : Friday, February 4, 2022 - 3:18:06 AM
Long-term archiving on: : Thursday, June 17, 2010 - 6:53:14 PM
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Sunday, November 1, 2009 - 1:43:37 PM
Last modification on : Friday, February 4, 2022 - 3:18:06 AM
Long-term archiving on: : Thursday, June 17, 2010 - 6:53:14 PM
File
BCCP-AICT06.pdf
Files produced by the author(s)