Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Seminarium "Algorytmika"

Research seminar (FRIDAYS, usually biweekly at 14.15 in room 5060 or online)

For schedule or link to online meetings, see https://semalgo.wordpress.com/

If you want  to get notifications of the talks sign up to the mailing list algorytmy@mimuw.edu.pl 

Rules for PhD studens: https://www.mimuw.edu.pl/~mp248287/algorithmsSeminarRules.pdf

Google calendar: https://calendar.google.com/calendar/embed?src=q1pbv62cra5jf9satch9ip49m...

YouTube cannel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp


Lista referatów

  • 2011-12-08, godz. 12:15, 5870

    Aleksander Madry (Microsoft Research New England i EPFL)

    Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs

    In this talk, I'll describe a new technique for approximating the maximum flow in capacitated, undirected graphs. I'll then use this technique to develop the asymptotically fastest-known algorithm for solving this problem. Our approach is based on treating the graph as a network of resistors and so...

  • 2011-12-01, godz. 12:15, 5870

    Krzysztof Rządca (Uniwersytet Warszawski)

    Teoriogrowe mechanizmy zwiększania dostępności danych w rozproszonych systemach replikacyjnych

    W systemach przechowywania danych w architekturze peer-to-peer, użytkownicy zwiększają dostępność danych przez wzajemne ich replikowanie. Centralny system pośredniczący w zawieraniu umów replikacyjnych może zoptymalizować dostępność danych tak, by wszyscy użytkownicy mieli podobny poz...

  • 2011-11-24, godz. 12:15, 5870

    Riste Skrekovski (Uniwersytet Warszawski)

    Some results on fullerene graphs

    Fullerene graphs are 3-connected planar cubic graphs with all faces of size 5 or 6. Motivation to study this class of graphs came from chemistry. In my talk I will present some bounds on the invariants as diameter, the independence number, the smallest eigenvalue, bipartite edge frustration, and sat...

  • 2011-11-17, godz. 12:15, 5870

    Christian Wulff-Nilsen (University of Southern Denmark)

    Approximate Distance Oracles with Faster Preprocessing and Query Time

    Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k>=2, we show that for some constant c, a (2k-1)-approximate distance oracle for G of size O(kn^{1 + 1/k}) can be constructed in O(\min\{kmn^{1/k},\sqrt km + kn^{1 + c/\sqrt k}\}) time and ca...

  • 2011-11-03, godz. 12:15, 5870

    Wojciech Tyczyński (Uniwersytet Warszawski)

    Wykorzystanie teorii automatów do przetwarzania dokumentów XML cz. II

    Tematem seminarium będzie algorytm, który dla zadanego zapytania XPath \phi oraz dokumentu XMLowego t zwraca zbiór wierzchołków t, które spełniają zadaną formułę. Silniki, które zawierają algorytmy ewaluacji zapytań XPath są wbudowane we wszystkie przeglądarki internetowe. Jednakże ...

  • 2011-10-27, godz. 12:15, 5870

    Wojciech Tyczyński (Uniwersytet Warszawski)

    Wykorzystanie teorii automatów do przetwarzania dokumentów XML

    Tematem seminarium będzie algorytm, który dla zadanego zapytania XPath \phi oraz dokumentu XMLowego t zwraca zbiór wierzchołków t, które spełniają zadaną formułę. Silniki, które zawierają algorytmy ewaluacji zapytań XPath są wbudowane we wszystkie przeglądarki internetowe. Jednakże ...

  • 2011-10-20, godz. 12:15, 5870

    Attila Bernáth (Uniwersytet Warszawski)

    Degree-bounded spanning trees and matroids

    Consider the problem of finding a minimum cost spanning tree in a graph with the additional requirement that the degree of each node in the tree should not exceed an upper bound given in advance. This problem is hard: already the problem of deciding whether such a tree exists is NP-complete, so it d...

  • 2011-06-02, godz. 12:15, 5870

    Saket Saurabh ( Institute of Mathematical Sciences, Chennai, India)

    Chromatic Coding

    Alon, Yuster and Zwick developed the method of color-coding to give a 2^O(k)n^O(t)  time algorithm for subgraph isomorphism problem when the subgraph we are looking for has treewidth t and size k. We develop a variation of this method, called Chromatic Coding, where one is interested in just proper...

  • 2011-05-12, godz. 12:15, 5870

    Jakub Łącki (Uniwersytet Warszawski)

    Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time

    We present a deterministic O(n log log n) time algorithm for finding shortest cycles and minimum cuts in planar graphs. The algorithm improves the previously known fastest algorithm by Italiano et al. in STOC'11 by a factor of log n. This speedup is obtained through the use of dense distance gra...

  • 2011-05-05, godz. 12:15, 5870

    Piotr Sankowski (Uniwersytet Warszawski)

    Dynamiczne algorytmy tekstowe

    Tematem tego seminarium będzie technika stworzona przez K. Mehlhorn, R. Sundar i C. Uhrigw pracy "Maintaining dynamic sequences under equality tests in polylogarithmic time", która umożliwia dynamiczne utrzymywanie informacji o sekwencjach i pozwala na wykonywanie na nich testów r...

Strony