Approximation strategies for routing edge disjoint paths in complete graphs

Adrian Kosowski

doi:10.1007/11780823_11

Approximation strategies for routing edge disjoint paths in complete graphs

Abstract

Praca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.

Citations

0

CrossRef
0

Web of Science
0

Scopus

Author (1)

Adrian Kosowski dr inż.

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Monographic publication
Type:: rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
Title of issue:: SIROCCO 2006 : Structural Information and Communication Complexity : 13th International Colloquium : Proceeding, Chester, UK 2-5 July, 2006 strony 130 - 142
Language:: English
Publication year:: 2006
Bibliographic description:: Kosowski A.: Approximation strategies for routing edge disjoint paths in complete graphs// Structural Information and Communication Complexity/ ed. eds: P. Flocchini, L. Gasieniec. Berlin-Heidelberg: Springer-Verlag, 2006, s.130-142
DOI:: Digital Object Identifier (open in new tab) 10.1007/11780823_11
Verified by:: Gdańsk University of Technology