[Facets-of-complexity] Monday Lecture & Colloquium - Dec 3, 2018 - TODAY

[Günter Rote <rote@inf.fu-berlin.de>]

You are cordially invited to our Monday Lecture & Colloquium on Dec 3rd
at 14:15 h & 16:00 h at FU Berlin.

Lecture: Monday, Dec 3rd - 14:15 h
   ===============================================
   László Kozma (Freie Universität Berlin):

   Self-adjusting data structures: trees and heaps
   ===============================================

Abstract:
Binary search trees (BSTs) and heaps are perhaps the simplest
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 them remain open. What is the
best strategy for updating a BST in response to queries? Is there a
single strategy that is optimal for every possible scenario? Are
self-adjusting trees ("splay trees", Sleator and Tarjan, 1983) optimal?
In which cases can we improve upon the logarithmic worst-case cost per
operation? Our understanding of heaps is even more limited. Fibonacci
heaps (and their relatives) are theoretically optimal in a worst-case
sense, but they perform operations outside the "pure" comparison-based
heap model (in addition to being complicated in practice).
Is there a simple, "self-adjusting" alternative to Fibonacci heaps?
Is there, by analogy to BSTs, a heap that can adapt to regularities in
the input? Are the two problems related? In my talk I will present some
old and new results pertaining to this family of questions.

Coffee & Tea Break

Colloquium: 16:00 h
   ===============================================================
   Petr Gregor (Charles University, Prague):

   Incidence colorings of subquartic graphs and Cartesian products
   ===============================================================

Abstract:
Two incidences (u,e) and (v,f) of vertices u, v and edges e, f
(respectively) are adjacent if u=v, or e=f, or uv is one of edges e, f.
An incidence coloring of a graph G is a coloring of its incidences such
that adjacent incidences have distinct colors. We show that every graph
of maximal degree 4 has an incidence coloring with 7 colors.
Furthermore, we present sufficient conditions for Cartesian product
graphs to have incidence colorings with Delta+2 colors where Delta is
the maximal degree. In particular, we confirm a conjecture of Pai et al.
on incidence colorings of hypercubes.
Joint work with B. Lužar and R. Soták.

Location:
Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin