Organizatorzy

dr hab. Michał Pilipczuk, prof. ucz.

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

17 stycznia 2019 12:15
Adrian Vladu (Boston University)
Discrepancy and Optimization
We consider the problem of minimizing the discrepancy of a set system. In 1985, Spencer proved that for m sets over a universe of n elements, one can always achieve a coloring with discrepancy O(sqrt(n …
29 listopada 2018 12:15
Krszysztof Fleszar (Univerisity of Warsaw)
A PTAS for TSP with hyperplane neighborhoods
A PTAS for TSP with hyperplane neighborhoods In TSP with neighborhoods, we are asked for a shortest tour visiting a given set of regions (i.e., neighborhoods). When the neighborhoods are lines in 2D, the problem …
25 października 2018 12:15
Stéphan Thomassé (ENS Lyon)
EPTAS for Max Clique on Disks and Unit Balls
We propose a polynomial-time algorithm which takes as input a finite set of points of R3 and computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the …
11 października 2018 12:15
Paweł Rzążewski (MIMI PW)
Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization
In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v\in V(G). The task is to find a homomorphism \phi:V(G)\to V(H) …
19 lipca 2018 12:15
Jan van der Brand (KTH)
Improved Algorithms for Dynamic Matrix Inverse
The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems, such as maintaining the …
11 czerwca 2018 12:15
Krzysztof Kiljan, Wojciech Nadara, Michał Ziobro
Three talks from Symposium on Experimental Algorithms (SEA'18)
Krzysztof Kiljan, Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes …
19 kwietnia 2018 12:15
Laszlo Kozma (TU Eindhoven)
Trees and heaps: the many faces of basic data structures
Binary search trees (BSTs) and heaps are the canonical comparison-based implementations of the dictionary and the priority queue data types. They are among the most extensively studied structures in computer science, yet, many basic questions about …
5 kwietnia 2018 12:15
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, …
15 marca 2018 12:15
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, …
8 marca 2018 12:15
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 …
1 marca 2018 12:15
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. …
8 lutego 2018 12:15
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 …
7 grudnia 2017 12:15
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. …
23 listopada 2017 12:15
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 …
9 listopada 2017 12:15
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 …