Edge ranking and searching in partial orders

Dariusz Dereniowski

doi:10.1016/j.dam.2008.03.007

Edge ranking and searching in partial orders

Abstrakt

Artykuł jest poświęcony problemowi konstrukcji optymalnej (wymagającej minimalnej ilości porównań/zapytań) strategii wyszukiwania elementu w częściowym porządku. W pracy wskazano związki pomiędzy tym problemem oraz uporządkowanym kolorowaniem krawędzi grafów, co implikuje liniowy algorytm dla częściowych porządków o strukturze drzewa. Pokazano również, że znalezienie optymalnej strategii jest problemem obliczeniowo trudnym dla częściowego porządku posiadającego element maksymalny i podano przybliżony algorytm dla tego przypadku.

Cytowania

2 0

CrossRef
0

Web of Science
2 7

Scopus

Autor (1)

Dariusz Dereniowski prof. dr hab. inż.

Cytuj jako

Pełna treść

pobierz publikację

pobrano 31 razy

Wersja publikacji: Accepted albo Published Version
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2008.03.007
Licencja: Copyright (2008 Elsevier B.V)

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

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 156, strony 2493 - 2500,
ISSN: 0166-218X
Język:: angielski
Rok wydania:: 2008
Opis bibliograficzny:: Dereniowski D.: Edge ranking and searching in partial orders// DISCRETE APPLIED MATHEMATICS. -Vol. 156., nr. iss. 13 (2008), s.2493-2500
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.dam.2008.03.007
Weryfikacja:: Politechnika Gdańska