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

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...