Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
nr T. 1,
strony 15 - 20,
ISSN: 1732-1166 - Język:
- angielski
- Rok wydania:
- 2011
- Opis bibliograficzny:
- 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
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 109 razy