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.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1016/j.dam.2007.07.013
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie z listy filadelfijskiej
- Język
- angielski
- Rok wydania
- 2007
Źródło danych: MOSTWiedzy.pl - publikacja "Easy and hard instances of arc ranking in directed graphs" link otwiera się w nowej karcie
