Organizatorzy

dr hab. Marcin Pilipczuk, prof. UW

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

17 listopada 2016 12:15
Erik Jan van Leeuwen
Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
We consider the recognition problem for two graph classes that generalize split and unipolar graphs, respectively. First, we consider the recognizability of graphs that admit a monopolar partition: a partition of the vertex set into …
3 listopada 2016 12:15
Łukasz Kowalik
On the Fine-Grained Complexity of Rainbow Coloring
The Rainbow k-Coloring problem asks whether the edges of a given graph can be colored in k colors so that every pair of vertices is connected by a rainbow path, i.e., a path with all …
20 października 2016 12:15
Daniel Marx
The Optimality Program in Parameterized Algorithms
Parameterized complexity analyzes the computational complexity of NP-hard combinatorial problems in finer detail than classical complexity: instead of expressing the running time as a univariate function of the size $n$ of the input, one or …
13 października 2016 12:15
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 …
31 maja 2012 12:15
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. …
24 maja 2012 12:15
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 …
10 maja 2012 12:15
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 …
8 marca 2012 12:15
Marcin Mucha (Uniwersytet Warszawski)

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 …
23 lutego 2012 12:15
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 …
12 stycznia 2012 12:15
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 - …
8 grudnia 2011 12:15
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 …
1 grudnia 2011 12:15
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 …
24 listopada 2011 12:15
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 …
17 listopada 2011 12:15
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 …
3 listopada 2011 12:15
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. …