Short Length Menger's Theorem and Reliable Optical Routing

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

Result language
angličtina
Original language name
Short Length Menger's Theorem and Reliable Optical Routing
Original language description
We deal with a generalization of the minimum path coloring problem: given a graph and a set of pairs of vertices, we are asked to connect each pair by $k$ edge disjoint paths of the same color; the objective is to minimize the number of colors while maintaining the property that paths of the same color are edge disjoint. The underlying problem is that of finding several disjoint paths between a given pair of vertices, which is closely related to the Menger's theorem. The Menger's theorem does not say anything about the length of the paths; the question about the length of the paths is also addressed in the paper.
Czech name
Mengerova věta pro krátké cesty a spolehlivé optické směrování
Czech description
Studujeme zobecnění problému barvení cest minimálním počtem barev: pro daný graf a množinu dvojic vrcholů chceme spojit každou dvojici k disjunktními cestami téže barvy; úkolem je minimalizovat počet použitých barev za podmínky, že cesty stejné barvy jsou hranově disjunktní. Základním problémem je hledání disjunktních cest mezi jednou dvojicí, problém úzce spjatý s Mengerovou větou. Mengerova věta neříká nic o délce těchto cest; článek dává odhady na délku těchto cest.

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/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

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

Similar results(10)