Dariusz Dereniowski - Profil naukowy - MOST Wiedzy

Wyszukiwarka

Media społecznościowe

Wybrane publikacje

  • Fast collaborative graph exploration

    - INFORMATION AND COMPUTATION - Rok 2015

    We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Drawing maps with advice

    Rozważamy następujący problem obliczeniowy. Agent zostaje umieszczony w wierzchołku nieznanego mu grafu. Wierzchołki grafu są nierozróżnialne, natomiast krawędzie posiadają numery portów. Zadaniem agenta jest wyznaczenie mapy, tzn. obliczenie izomorficznej kopii grafu, lub obliczenie dowolnego drzewa spinającego grafu. Bez dodatkowej informacji zadań tych nie można wykonać. W artykule wyznaczamy oszacowania na minimalną liczbę...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Edge ranking and searching in partial orders

    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...

    Pełny tekst do pobrania w serwisie zewnętrznym

Uzyskane stopnie/tytuły naukowe

wyświetlono 1119 razy