📖
All-to-All Routing and Coloring in Weighted Trees of Rings
Bruno Beauquier, Stéphane Pérennes, David Tóth

All-to-All Routing and Coloring in Weighted Trees of Rings

Science & Mathematics Published 1999 Verification Pending

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → 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 »