Searching in tree-like posets using edge rankings

• Autorzy: Dereniowski D.

Warianty tytułu

PL

Szukanie w częściowych porządkach o strukturze drzewa z wykorzystaniem uporządkowanego kolorowania krawędzi grafów

• Języki publikacji: EN

Abstrakty

EN

Searching in a partially ordered set (V,

PL

Problem szukania elementu x w zbiorze częściowo uporządkowanym (V,

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2006
• Tom: T. 10
• Strony: 485--489
• Opis fizyczny: Bibliogr. 8 poz., 2 tab.

Twórcy

autor

Dereniowski D.

• Department of Algorithms and System Modeling, Gdańsk University of Technology

Bibliografia

• [1] Ben-Asher Y., Farchi E., Newman I.: Optimal search in trees, SIAM J. Comp. 6 (1999) 2090-2102.
• [2] Bezicr B.: Software Testing Techniques, Van Nostrand Reinhold (1990).
• [3] Franki P.G., Weyuker EJ.: Provable improvements on branch testing, IEEE Transactions on Software Engineering 19 (1993) 962-975.
• [4] Carmo R., Donadelli J., Kohayakawa Y., Laber E.: Searching in random partially ordered sets, Theoretical Computer Science 321(1) (2004) 41-57.
• [5] Lam T.W., Yue F.L.: Edge ranking of graphs is hard, Discrete Appl. Math. 85 (1998) 71-86.
• [6] Iyer A.V., Ratliff H.D., Vijayan G.: On an edge ranking problem of trees and graphs, Discrete Appl. Math. 30 (1991) 43-52.
• [7] de la Torre P., Greenlaw R., Schaffer A.A.: Optimal edge ranking of trees in polynomial time, Algorithmica 13 (1995) 529-618.
• [8] Lam T.W., Yue F.L.: Optimal edge ranking of trees in linear time, Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998) 436-445.