Nie jesteś zalogowany |
Shortest paths, edge weights, and models of computation
- Prelegent(ci)
- Adam Karczmarz
- Afiliacja
- Institute of Informatics
- Język referatu
- angielski
- Termin
- 22 stycznia 2026 14:30
- Pokój
- p. 2180 (sala RW)
- Tytuł w języku polskim
- Najkrótsze ścieżki a wagi krawędzi i modele obliczeń
- Seminarium
- Kolokwium Wydziału MIM UW
Obliczanie najkrótszej ścieżki jest jednym z najprostszych problemów optymalizacyjnych na grafach. Mimo to, dokładna złożoność obliczeniowa tego problemu nie jest w pełni zrozumiana. Najlepsze znane oszacowania czasu działania różnią się w zależności od przyjętego modelu obliczeń oraz dziedziny dopuszczalnych wag krawędzi. W referacie omówię to zjawisko, które występuje także w innych problemach optymalizacyjnych rozwiązywalnych w czasie wielomianowym. Wspomnę również o kilku niedawnych osiągnięciach algorytmicznych w tym zakresie.
Computing the shortest path is one of the simplest optimization problems on graphs. Nevertheless, the exact computational complexity of this problem is not fully understood. The best-known running-time bounds differ depending on the adopted computational model and the domain of allowed edge weights. In this talk, I will discuss this phenomenon, which also occurs in other optimization problems solvable in polynomial time. I will also mention a few recent algorithmic advances in this area.
