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
-
Oct. 13, 2016, 12:15 p.m.
Jakub Radoszewski (University of Warsaw)
Pattern matching on weighted sequences
Abstract: In a weighted sequence, for every position of the sequence and every letter of the alphabet, a probability of occurrence of this letter at this position is specified. Sequences of this type, also called …
-
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 …
