All-to-All Routing and Coloring in Weighted Trees of Rings
Overview & Synopsis
A tree of rings is an undirected graph obtained from the union of rings, which intersect two by two in at most one node, such that any two nodes are connected by exactly two edge-disjoint paths. In this paper, we consider symmetric directed trees of rings with weighted nodes. A routing for a weighted digraph is a collection of directed paths (dipaths), such that for each ordered pair of nodes (x_1,x_2) with respective weights w_1 and w_2, there are w_1w_2 dipaths (possibly not distinct) from x_1 to x_2. Motivated by the Wavelength Division Multiplexing (WDM) technology in all-optical networks, we study the problem of finding a routing which can be colored by the fewest number of colors so that dipaths of the same color are arc-disjo- int. We prove that this minimum number of colors (wavelengths) is equal to the maximum number of dipaths that share one arc (load), minimized over all routings. The problem can be efficiently solved (dipaths found and colored) using cut properties.
hal.science)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | All-to-All Routing and Coloring in Weighted Trees of Rings |
|---|---|
| Author / Organization | Bruno Beauquier, Stéphane Pérennes, David Tóth |
| Subject & Discipline | Multidisciplinary Academic Open Research |
| Categories | Science & Mathematics |
| Publication Year | 1999 |
| License / Rights | Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
HAL Open Science
(hal.science)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-67729 |
| Original Source Link | Visit Source Page on hal.science » |