On the Minimum Load Coloring Problem

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00004713" target="_blank" >RIV/00216208:11320/07:00004713 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On the Minimum Load Coloring Problem
Original language description
Given a graph G=(V,E) with n vertices, m edges and maximum vertex degree d, the load distribution of a coloring is a pair df=(rf,bf), where rf is the number of edges with at least one end-vertex colored red and bf is the number of edges with at least oneend-vertex colored blue. Our aim is to find a coloring f such that the (maximum) load, is minimized. This problems arises in Wavelength Division Multiplexing (WDM), the technology currently in use for building optical communication networks. After proving that the general problem is NP-hard we give a polynomial time algorithm for optimal colorings of trees and show that the optimal load is at most 1/2+(d/m)log2n. For graphs with genus g>0, we show that a coloring with load OPT(1+o(1)) can be computed in O(n+glogn)-time.
Czech name
O barveních minimalizujících zátěž
Czech description
Pro daný graf G=(V,E) s n vrcholy, m hranami a maximálním stupňěm d hledáme barvení, které minimalizuje zátěž.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GD201%2F05%2FH014" target="_blank" >GD201/05/H014: Collegium Informaticum</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)