A note on fast approximate backbone coloring of split graphs with star--like backbones

Krzysztof Turowski

A note on fast approximate backbone coloring of split graphs with star--like backbones

Abstract

Dla grafu G = (V, E) z wyróżnionym podgrafem H, kolorowanie szkieletowe jest zdefiniowane jako odwzorowanie c spełniające |c(u) - c(v)| > 1 dla każdej krawędzi z E(H) oraz |c(u) - c(v)| > 0 dla każdej krawędzi z E(G). W pracy przedstawiono 1-przybliżony algorytm kolorowania szkieletowego split grafów ze skojarzeniem w szkielecie o złożoności O(|V|) oraz 1-przybliżony algorytm dla split grafów z rozłącznymi gwiazdami w szkielecie.

Author (1)

Krzysztof Turowski 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

SZKIELETOWE KOLOROWANIE GRAFÓW

Details

Category:: Articles
Type:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Published in:: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne no. T. 1, pages 15 - 20,
ISSN: 1732-1166
Language:: English
Publication year:: 2011
Bibliographic description:: Turowski K.: A note on fast approximate backbone coloring of split graphs with star--like backbones// Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne. -Vol. T. 1., (2011), s.15-20
Verified by:: Gdańsk University of Technology