O barveních minimalizujících zátěž

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On the Minimum Load Coloring Problem

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On the Minimum Load Coloring Problem

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GD201%2F05%2FH014" target="_blank" >GD201/05/H014: Collegium Informaticum</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

Kód důvěrnosti údajů

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

Název periodika

Journal of Discrete Algorithms

ISSN

1570-8667

e-ISSN

—

Svazek periodika

5

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

533-545

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—