You are not logged in | Log in
Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw Logo of the Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw
Return to the list of seminars

Seminar Algorithms

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 cannel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp

 

 

Organizers

Information

Fridays, 2:15 p.m. , room: 5060

Home page

https://semalgo.wordpress.com/

List of talks
  • Nov. 17, 2016, 12:15 p.m.
    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 …
  • Nov. 3, 2016, 12:15 p.m.
    Ł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 …
  • Oct. 20, 2016, 12:15 p.m.
    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 …
  • 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. …

Careers

Website

© 2024 University of Warsaw. All rights reserved.