You are not logged in |
Shortest paths, edge weights, and models of computation
- Speaker(s)
- Adam Karczmarz
- Affiliation
- Institute of Informatics
- Language of the talk
- English
- Date
- Jan. 22, 2026, 2:30 p.m.
- Room
- room 2180 (sala RW)
- Title in Polish
- Najkrótsze ścieżki a wagi krawędzi i modele obliczeń
- Seminar
- Colloquium Of MIM
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.
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.
