Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. ucz.

Information

Home page

Research fields

• Algorithmics

List of talks

• Dec. 15, 2016, 12:15 p.m.
  Marcin Wrochna (University of Warsaw)
  tw)*n time (Algorithms for graphs and matrices in poly)
  Abstract: Knowing how small treewidth can be exploited algorithmically in NP-hard problems, we ask about speeding up classical polynomial-time algorithms to (quasi-)linear in the graph size, while keeping the dependency on treewidth polynomial. We provide …

  ---

• Dec. 1, 2016, 12:15 p.m.
  Bartosz Walczak (Uniwersytet Jagielloński)
  Coloring graphs with geometric representations and related problems
  Colorings of graphs represented by geometric objects have been studied since the 1960s for both theoretical and practical reasons. In particular, geometric representations lead to natural examples of classes of graphs that are χ-bounded (near-perfect), …

  ---

• Nov. 24, 2016, 12:15 p.m.
  Andrzej Grzesik
  Minimum number of edges that occur in odd cycles
  For any fixed k>1 every graph without a cycle on 2k+1 vertices has at most n^2/4 edges. In 1992, Erdos, Faudree and Rousseau conjectured that if a graph has at least n^2/4 + 1 edges, …

  ---

• 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 …

  ---