Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

MiniSymposium on Combinatorial Algorithms

Friday, February 24th 2017

All talks are in CAB G11.

10:00-10:20 Different Tree Packing Conjectures
Anastasia Moskovaya, EPFL

In 1976, Gyárfás and Lehel conjectured that any family of trees T1,.., Tn with each Ti on i vertices can decompose the complete graph on n vertices in an edge-disjoint manner. In other words, any such family of trees packs into Kn. A few years earlier, in 1967 a related conjecture was posed by Ringel. He said that considering a tree T on n vertices, 2n−1 isomorphic copies of it pack into K2n−1. Since decades, the way to look at this conjecture is through another conjecture, the Graceful Tree Conjecture by Kotzig. Using a cyclical decomposition of K2n−1, the Graceful Tree Conjecture implies Ringel’s conjecture. I will discuss these conjectures and some of the important known results, and then explore a new way of looking at the Graceful Tree Conjecture through the notion of flip graphs, based on a local operation on graceful trees.

10:25-10:45 Finding the Sink of a USO with a Hamming Ball
Kilian Risse, ETHZ

A unique sink orientation (USO) is an orientation of the n-dimensional hypercube such that every nonempty face has a unique sink. The main algorithmic problem is to find the global sink of the USO. In this talk, I present a simple randomized algorithm to find the global sink of the USO.

10:45-11:00 Coffee Break
11:00-11:20 Partial and Constrained Level Planarity
Guido Brückner, KIT

Let G=(V,E) be a graph and ℓ: V → {1,...,k} a leveling. In a level-planar drawing of G each vertex v lies on the horizontal line with y-coordinate ℓ(v), and edges are drawn as non-crossing y-monotone curves. In the problem Constrained Level Planarity (CLP), we are further given a partial ordering ≺i of Vi := ℓ-1(i) for i ∈ {1,...,k}, and we seek a level-planar drawing where the order of the vertices on ℓi is a linear extension of ≺i. A special case of this is Partial Level Planarity (PLP), where we are asked to extend a given level-planar drawing ℋ of a subgraph H ⊆ G to a complete drawing of G without modifying ℋ. We give a simple algorithm with running time O(n5) for CLP of single-source graphs. We introduce a modified type of PQ-tree data structure that can efficiently handle the arising constraints to improve the running time to O(n + k l), where l is the size of the constraints. We complement this by showing that PLP is NP-complete even in very restricted cases.

11:25-11:45 Algorithmic Proof for the Existence of Six-way Equipartitions
Gábor Damásdi, ELTE

Given a set of points in the plane, one can always find three concurrent lines such that they divide the set into six equal parts. This theorem was proved by a topological argument originally. I will present a similar but algorithmic proof. My algorithm runs in O(n2log(n)) time.

Last modified: Tue Feb 21 13:58:45 CET 2017  Valid HTML5