You are not logged in |
Research seminar (Fridays, at 14.15 in room 5060)
For schedule or link to online meetings, see https://semalgo.wordpress.com/
If you want to get notifications, 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=q1pbv62cra5jf9satch9ip49ms%40group.calendar.google.com&ctz=Europe%2FWarsaw
YouTube channel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp
Organizers
- dr hab. Michał Pilipczuk, prof. ucz.
Information
Fridays, 2:15 p.m. , room: 5060Home page
https://semalgo.wordpress.com/List of talks
-
May 31, 2012, 12:15 p.m.
Anna Zych & Attila Bernath (Uniwersytet Warszawski)
The Maximum Independent Set problem on intersection graphs & Covering minimum cost arborescences
The Maximum Independent Set problem on intersection graphs I will talk about the Maximum Independent Set problem on intersection graphs. An independent set is a set of vertices in the graph that are pairwise disjoint. …
-
May 24, 2012, 12:15 p.m.
Andras Sebo (CNRS, Laboratoire G-SCOP, Grenoble)
TSP and related problems via Matroids, Matchings and Extensions
I present improved approximation guarantees for the graphic TSP and some related problems. For the graphic TSP itself, the new approximation ratio is $7/5$. For a generalization, the connected-$T$-join problem, we obtain the first nontrivial …
-
May 10, 2012, 12:15 p.m.
Gruia Calinescu (Illinois Institute of Technology)
Minimum Power Strong Connectivity
Given a directed simple graph G=(V,E) and a nonnegative-valued cost function the power of a vertex u in a directed spanning subgraph H is given by the maximum cost of an arcs of H exiting …
-
March 8, 2012, 12:15 p.m.
Marcin Mucha (Uniwersytet Warszawski)
Graphic) TSP approximatio ()
During the recent year, a lot of progress has been made on approximating the Traveling Salesman Problem and the Traveling Salesman Path Problem, and in particular their graphic variants. In this talk I will briefly …
-
Feb. 23, 2012, 12:15 p.m.
Wojciech Tyczynski (Uniwersytet Warszawski)
Computing factorization forest of a small depth
Assume we have a finite set Q and set of all binary relations over Q: R_Q. Let w be the word over alphabet R_Q. An evaluation of word w is the composition of all letters …
-
Jan. 12, 2012, 12:15 p.m.
Marcin Pilipczuk (Uniwersytet Warszawski)
A glimpse on my PhD thesis
In my talk I will present the main results of my PhD thesis. I plan to focus mostly on the background of my research, motivation, and present a very general overview of the techniques - …
-
Dec. 8, 2011, 12:15 p.m.
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 …
-
Dec. 1, 2011, 12:15 p.m.
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 poziom dostępności. Jeśli …
-
Nov. 24, 2011, 12:15 p.m.
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 …
-
Nov. 17, 2011, 12:15 p.m.
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 …
-
Nov. 3, 2011, 12:15 p.m.
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. …
-
Oct. 27, 2011, 12:15 p.m.
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. …
-
Oct. 20, 2011, 12:15 p.m.
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. …
-
June 2, 2011, 12:15 p.m.
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 …
-
May 12, 2011, 12:15 p.m.
Jakub Łącki (Uniwersytet Warszawski)
n log log n) Tim (Min-cuts and Shortest Cycles in Planar Graphs in O)
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 …
