Free Online Productivity Tools
i2Speak
i2Symbol
i2OCR
iTex2Img
iWeb2Print
iWeb2Shot
i2Type
iPdf2Split
iPdf2Merge
i2Bopomofo
i2Arabic
i2Style
i2Image
i2PDF
iLatex2Rtf
Sci2ools
129
Voted
AICT
2006
IEEE
2006
IEEE
Optimal Solution of the Maximum All Request Path Grooming Problem
— 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. Keywords : grooming, requests, path, capacity, coloration of interval graphs.
Real-time TrafficRelated Content
| Added | 10 Jun 2010 |
| Updated | 10 Jun 2010 |
| Type | Conference |
| Year | 2006 |
| Where | AICT |
| Authors | Jean-Claude Bermond, Michel Cosnard, David Coudert, Stéphane Pérennes |
Comments (0)
Researcher Info
|
