Lista referatów

• 2018-04-05, godz. 12:15, 5870

  Wiktor Zuba (MIMUW)

  Hamilitonian cycles of middle-levels subgraphs of hypercubes

  The n-dimension hypercube graph is the graph with vertices represented by sequences of n bits, with edges connecting those vertices, which representations differ at exactly one position. We can divide the graph into (n+1) levels, where k-th level contains those vertices, which have exactly k one...

• 2018-03-15, godz. 12:15, 5870

  Marthe Bonamy (LaBRI, CNRS, Universite de Bordeaux)

  Distributed coloring in sparse graphs with fewer colors

  Distributed coloring in sparse graphs with fewer colors Abstract : We are concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the p...

• 2018-03-08, godz. 12:15, 5870

  Magnus Wahlström (University of London)

  Fine-grained structure of NP-hard SAT problems

  Say that a problem SAT(\Gamma), for a constraint language \Gamma, admits an improved algorithm if it can be solved in O(c^n) time on n variables for some c<2, and that it is hard otherwise. Many examples exist, both of problems SAT(\Gamma) with improved algorithms and problems hypothesised...

• 2018-03-01, godz. 12:15, 5870

  Marc Heinrich (LIRIS )

  Online graph coloring with bichromatic exchanges

  Greedy algorithms for the graph coloring problem require a large number of colors, even for very simple classes of graphs. For example, any greedy algorithm coloring trees requires $\Omega(\log n)$ colors in the worst case. We consider a variation of the First-Fit algorithm in which the algorithm is...

• 2018-02-08, godz. 12:15, 5870

  Lucas Pastor

  Disproving the normal graph conjecture

  A graph G is said to be normal if there exists two coverings, C and S of its vertex set such that, every member of C induces a clique, every member of S induces a stable set, and every clique of C intersects every stable set of S. De Simone and Körner conjectured in 1999 that a graph G is norma...

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

  Marcin Pilipczuk (Uniwrsytet Warszawski)

  The Erdős-Hajnal conjecture for caterpillars and their complements

  The celebrated Erdos-Hajnal conjecture states that for every proper hereditary graph class GG there exists a constant eps>0 such that every graph G in GG contains a clique or an independent set of size |V(G)|^eps. Recently, there has been a growing interest in the symmetrized variant of th...

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

  Irene Muz

  Half-integral linkages in highly connected directed graphs

  We study the half-integral k-Directed Disjoint Paths Problem (1/2 kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where k=2, and the input graph is L-strongly connected, for any L >= 1. We show that when the integrality condition i...

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

  Bart M. P. Jansen (Eindhoven University of Technology)

  Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations

  We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs F, the F-Deletion problem is the following: given a graph G and integer k, is it possible to delete k vertices from G ...

• 2017-07-06, godz. 12:15, 5870

  Brynmor Chapman (Massachusetts Institute of Technology)

  A Refutation of the Gotsman-Linial Conjecture

  A degree-$d$ polynomial threshold function is a function that can be written as the sign of a degree-$d$ polynomial on the Boolean hypercube.  Bounds on the sensitivity of polynomial threshold functions to small changes in their inputs have many applications in circuit complexity and learning t...

• 2017-06-08, godz. 12:15, 5870

  Marek Adamczyk (University of Warsaw)

  When the Optimum is also Blind: a New Perspective on Universal Optimization

  Consider the following variant of the set cover problem. We are given a universe $U={1,2,...,n}$ and a collection of subsets C={S_1,...,S_m} where each S_i is a subset of U. For every element u of U we need to find a set phi(u) from C such that u belongs to phi(u). Once we construct and fix the m...

Strony