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

  • 2017-05-11, godz. 12:15, 5870

    Till Miltzow (Universit ́e libre de Bruxelles)

    The Art Gallery Problem is $\exists \mathbb{R}$-complete

    The \emph{art gallery problem} is a classical problem in computational geometry, introduced in 1973 by Viktor Klee. Given a simple polygon \poly and an integer $k$, the goal is to decide if there exists a set $G$ of $k$ \emph{guards} within \poly such that every point $p\in \poly$ is seen by...

  • 2017-04-20, godz. 12:15, 5870

    Marcin Wrochna (University of Warsaw)

    A topological approach related to Hedetniemi's conjecture

    Hedetniemi's 50 years old conjecture states that the chromatic number of the tensor product of graphs G,H is the minimum of the chromatic numbers of G and H. The conjecture has many interesting connections with graph theory, especially with graph homomorphisms, where we consider more generally a...

  • 2017-03-23, godz. 12:15, 5870

    Paweł Rzążewski (Politechnika Warszawska)

    Fine-grained complexity of coloring disks, balls, and segments.

    On planar graphs, many classic algorithmic problems enjoy a certain ``square root phenomenon'' and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian Cycle, Dominating Set can be solved in time 2^{O(sq...

  • 2017-03-16, godz. 12:15, 5870

    Andreas Emil Feldmann (Charles University)

    The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems

    Given a directed graph G and a list (s1 , t1 ), . . . , (sk , tk ) of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of G that contains a directed si → ti path for every 1 ≤ i ≤ k. The special case Directed Steiner Tree (when we ask for paths from a ...

  • 2017-03-09, godz. 12:15, 5870

    Konstanty Junosza-Szaniawski (Politechnika Warszawska)

    Online coloring and L(2,1)-labeling of unit disk intersection graphs.

    We give a family of online algorithms for the classical coloring and the L(2,1)-labeling problems of unit disk intersection graphs. In the L(2,1)-labeling we ask for an assignment of non-negative integers to the vertices of the input graph, such that adjacent vertices get labels that differ by at le...

  • 2017-02-09, godz. 12:15, 5870

    Marthe Bonamy (Université de Bordeaux)

    Using region decomposition techniques for coloring problems

    We consider the problem of coloring the square of a planar graph that has no small cycle. We prove a conjecture of Dvorak, Kral, Nejedly, and Skrekovski that planar graphs of girth at least five are square (∆ + 2)-colorable for large enough maximum degree ∆. This completes the characterization o...

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

    O-joung Kwon (Technische Universitat Berlin)

    Parameterized complexity of Distance-Hereditary Vertex Deletion

    A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both vertices is the same as their distance in the original graph. Distance-hereditary graphs are exactly the graphs with rank-width at most 1. The Distance-Hereditary Vertex ...

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

    Marcin Wrochna (University of Warsaw)

    Algorithms for graphs and matrices in poly(tw)*n time.

    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 a fundamental toolbox for this purpose: ...

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

    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), which means that their chromatic number is...

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

    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, then already at least 2n^2/9 edges occur in cycles on 2k+1 vertices. In the talk I will disprove this conjecture ...