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

  • 2019-11-14, godz. 12:15, 5870

    Piotr Sankowski (University of Warsaw)

    Walking Randomly, Massively, and Efficiently

    We introduce an approach that allows for efficiently generating many independent random walks in big graph models, such as the Massive Parallel Computation (MPC) model. We consider the case where the space per machine is strongly sublinear in the number of vertices. In this case, many natural app...

  • 2019-11-07, godz. 12:15, 5870

    Marcin Pilipczuk (University of Warsaw)

    A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs

    We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph $G$, a set of clients $C\subseteq V(G)$, a set of facilities $F \subseteq V(G)$, and opening costs $w \colon F \to \mathbb{R}_{\geq 0}$, the goal is to find a subset $...

  • 2019-10-31, godz. 12:15, 5870

    François Dross (University of Warsaw)

    Trees in tournaments

    A tournament is an orientation of a complete graph. A digraph is n-unavoidable if it is contained (as a subdigraph) in every tournament of order n. The unavoidability of a digraph D is the minimum integer n such that D is n-unavoidable. It is well-known that the transitive tournament of order n is 2...

  • 2019-10-24, godz. 13:00, 5870

    Solon Pissis (CWI)

    Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication

    An elastic-degenerate (ED) string is a sequence of n sets of strings of total length N, which was recently proposed to model a set of similar sequences. The ED string matching (EDSM) problem is to find all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received som...

  • 2019-10-24, godz. 12:15, 5870

    Krzysztof Nowicki (UWr)

    Faster Algorithms for Edge Connectivity via Random 2-Out Contractions

    We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. We demonstrate the power of our new approach by obtaining better algor...

  • 2019-10-17, godz. 12:15, 5870

    Stéphane Bessy (LIRMM Montpellier)

    Triangle and cycle packing in tournaments: complexity and algorithms

    Given a tournament T and a positive integer k, we study different question dealing with packing (oriented) cycles in tournament: does T contain k vertex-disjoint cycles (k-VCT)? k arc-disjoint cycles (k-ACT)? k-arc-disjoint triangles (k-ATT)?, where a triangle is an oriented 3-cycle. These problems...

  • 2019-10-10, godz. 12:15, 5870

    Edouard Bonnet (ENS Lyon)

    Parameterized Complexity of Grundy Coloring and its variants

    (Connected/Partial/Weak) Grundy Coloring, b-Coloring, b-Chromatic Core, etc. are maximization coloring problems, where one asks for the worst case of a first-fit coloring strategy. They were introduced to analyze if some coloring heuristics have performance guarantee. We investigate the parameterize...

  • 2019-06-19, godz. 12:15, 5870

    Karol Węgrzycki (MIMUW)

    Recent Progress on Approximate APSP

    In this talk we prove the equivalence of computing the approximate (min,+)-product of two $n \times n$ matrices with arbitrary values and (min,max)-product. This yields a first subcubic strongly polynomial approximation for the all-pairs shortest path problem (APSP). The algorithm runs in time...

  • 2019-06-13, godz. 12:15, 5870

    Anita Liebenau (University of New South Wales)

    Enumerating graphs and other discrete structures by degree sequence

    How many d-regular graphs are there on n vertices? What is the probability that G(n,p) has a specific given degree sequence, where G(n,p) is the homogeneous random graph in which every edge is inserted with probability p? Asymptotic formulae for the first question are known when d=o(\sqrt(n)) an...

  • 2019-05-30, godz. 12:15, 5870

    Anish Mukherjee (Chennai Mathematical Institute, India)

    Solving connectivity problems via basic Linear Algebra

    We consider some classical graph connectivity problems like reachability, shortest path and disjoint paths in different settings. For the first two problems, we show efficient parallel algorithms in the dynamic framework, confirming a conjecture of Patnaik and Immerman ’94 for directed reachab...