Repozytorium publikacji - Politechnika Gdańska

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.

Autorzy

• prof. dr hab. inż. Dariusz Dereniowski link otwiera się w nowej karcie