
prof. dr hab. inż. Dariusz Dereniowski
Zatrudnienie
- Profesor w Katedra Algorytmów i Modelowania Systemów
Kontakt
- darderen@pg.edu.pl
Profesor
- Miejsce pracy
-
Budynek A Elektroniki
pokój EA 209 otwiera się w nowej karcie - Telefon
- (58) 347 19 56
- deren@eti.pg.edu.pl
Media społecznościowe
Wybrane publikacje
-
Fast collaborative graph exploration
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...
-
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ę...
-
From Pathwidth to Connected Pathwidth
W pracy przedstawiono dowód faktu, że spójna szerokość ścieżkowa grafu wynosi co najwyżek 2k+1, gdzie k jest jego szerokością ścieżkową. Dowód jest konstruktywny, tzn., został skonstruowany algorytm, który dla podanej na wejściu dekompozycji grafu o szerekości k zwraca dekompozycję spóją o szerekości co najwyżej 2k+1.
Uzyskane stopnie/tytuły naukowe
-
2013-01-22
Nadanie stopnia naukowego
dr hab. Informatyka (Dziedzina nauk technicznych) -
2006-07-11
Nadanie stopnia naukowego
dr Informatyka (Dziedzina nauk technicznych)
wyświetlono 1728 razy