Wyszukiwarka
Abstrakt
Artykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby kolorów równej 6.
Cytowania
-
1
CrossRef
-
0
Web of Science
-
1
Scopus
Cytuj jako
Pełna treść
pobierz publikację
pobrano 22 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2007.07.013
- Licencja
- Copyright (2007 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie z listy filadelfijskiej
- Opublikowano w:
-
DISCRETE APPLIED MATHEMATICS
nr 155,
strony 2601 - 2611,
ISSN: 0166-218X - Język:
- angielski
- Rok wydania:
- 2007
- Opis bibliograficzny:
- Dereniowski D.: Easy and hard instances of arc ranking in directed graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 155., (2007), s.2601-2611
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2007.07.013
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 96 razy