Easy and hard instances of arc ranking in directed graphs

Dariusz Dereniowski

doi:10.1016/j.dam.2007.07.013

Easy and hard instances of arc ranking in directed graphs

Abstract

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.

Citations

1

CrossRef
0

Web of Science
1

Scopus

Author (1)

Dariusz Dereniowski prof. dr hab. inż.

Cite as

Full text

download paper

downloaded 22 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2007.07.013
License: Copyright (2007 Elsevier B.V)

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie z listy filadelfijskiej
Published in:: DISCRETE APPLIED MATHEMATICS no. 155, pages 2601 - 2611,
ISSN: 0166-218X
Language:: English
Publication year:: 2007
Bibliographic description:: Dereniowski D.: Easy and hard instances of arc ranking in directed graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 155., (2007), s.2601-2611
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2007.07.013
Verified by:: Gdańsk University of Technology