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

Strony