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

Strony