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

If you want  to get notifications of the talks sign up to the mailing list 

Rules for PhD studens:

Google calendar:

YouTube cannel:

Lista referatów

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

    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 sets A,B such that G[A] is a disjoint union of cliques and G[B...

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

    Ł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 edges of different colors. Even for k=2, the best known algorithm runs in 2^{n^2} time. Our main result states th...

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

    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 more relevant parameters are defined and the running time i...

  • 2016-10-13, godz. 12:15, 5870

    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 position weight matrices (PWM), are commonly used to represent imprecise or uncert...

  • 2012-05-31, godz. 12:15, 5870

    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. In general graphs, the problem of finding the maximum independent set of vertices...

  • 2012-05-24, godz. 12:15, 5870

    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 approximation algorithm, with ratio $3/2$. This contain...

  • 2012-05-10, godz. 12:15, 5870

    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 u. The power of H is the sum of the power of its vertices. Power Assignment seeks to minimize the power of H ...

  • 2012-03-08, godz. 12:15, 5870

    Marcin Mucha (Uniwersytet Warszawski)

    (Graphic) TSP approximation

    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 survey the recent results and show in more detail the papers by Momke and Svensso...

  • 2012-02-23, godz. 12:15, 5870

    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 of w. A factorization forest for w is a laminar family of factors of w that contains {x} for every position x. A collation of the ...

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

    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 - without any technical details.The talk will be divided into two parts. The first part, titled `Beyond 2^n', is...