Wyszukiwarka
Abstrakt
A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution may be arbitrarily large. This negative result motivates us to investigate semi on-line algorithms, where a split graph is presented on-line but its clique number is given in advance. We prove that there does not exist a (2-ɛ)-competitive semi on-line algorithm of this type. Finally, a 2-competitive semi on-line algorithm is given.
Autorzy (2)
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ł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
nr 15,
strony 195 - 214,
ISSN: 1462-7264 - Język:
- angielski
- Rok wydania:
- 2013
- Opis bibliograficzny:
- Borowiecki P., Dereniowski D.: On-line ranking of split graphs// DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. -Vol. 15, nr. 2 (2013), s.195-214
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 77 razy