Edge ranking and searching in partial orders

Dariusz Dereniowski

doi:10.1016/j.dam.2008.03.007

Edge ranking and searching in partial orders

Abstract

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.

Citations

2 0

CrossRef
0

Web of Science
2 7

Scopus

Author (1)

Dariusz Dereniowski prof. dr hab. inż.

Cite as

Full text

download paper

downloaded 30 times

Publication version: Accepted or Published Version
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2008.03.007
License: Copyright (2008 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. 156, pages 2493 - 2500,
ISSN: 0166-218X
Language:: English
Publication year:: 2008
Bibliographic description:: Dereniowski D.: Edge ranking and searching in partial orders// DISCRETE APPLIED MATHEMATICS. -Vol. 156., nr. iss. 13 (2008), s.2493-2500
DOI:: Digital Object Identifier (open in new tab) 10.1016/j.dam.2008.03.007
Verified by:: Gdańsk University of Technology