Seminars
Seminars from previous years: 2025/26 2024/25 2023/24 2022/23 2021/22 2020/21 2019/20 2018/19 2017/18 2016/17 2015/16 2014/15 2013/14 2012/13 2011/12 2010/11
ACiD Seminars 2026/27.
| Tues 6th October 2026 13:00 MCS 3052 and online | |
| Tues 13th October 2026 13:00 MCS 3052 and online | Anouk Sommer (Karlsruhe Institute of Technology) Graph Redrawing on the Plane |
| Tues 20th October 2026 13:00 MCS 3052 and online | |
| Tues 27th October 2026 13:00 MCS 3052 and online | ACiD Meeting! |
| Tues 3rd November 2026 13:00 MCS 3052 and online | |
| Tues 10th November 2026 13:00 MCS 3052 and online | Frank Kammer (THM – University of Applied Sciences Mittelhessen) Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings We call a graph G separable if a balanced separator can be computed for G of size O(n^epsilon) with epsilon<1. Many real-world graphs are separable such as graphs of bounded genus, graphs of constant treewidth, and graphs excluding a fixed minor. In particular, the well-known planar graphs are separable. We present a succinct encoding of separable graphs G such that, after the encoding is computed, any number of depth-first searches (DFS) can be performed from any given start vertex, each in o(n) time and o(n) bits in the word RAM model. After the execution of a DFS, the succinct encoding of G is augmented such that the DFS tree is encoded inside the encoding while maintaining succinctness. Afterward, the encoding provides common DFS-related queries in constant time. These queries include queries such as lowest-common ancestor of two given vertices in the DFS tree or queries that output the lowpoint of a given vertex in the DFS tree. Furthermore, for planar graphs, we show that the succinct encoding can be computed in O(n) bits and expected linear time, and a compact variant can be constructed in O(n) time and bits. For other separable graph classes the runtime and space usage depends on the specific algorithms used to find balanced separators in these graphs. |
| Tues 17th November 2026 13:00 MCS 3052 and online | |
| Tues 24th November 2026 13:00 MCS 3052 and online | |
| Tues 1st December 2026 13:00 MCS 3052 and online | |
| Tues 8th December 2026 13:00 MCS 3052 and online | |
| Tues 12th January 2027 13:00 MCS 3052 and online | |
| Tues 19th January 2027 13:00 MCS 3052 and online | |
| Tues 26th January 2027 13:00 MCS 3052 and online | |
| Tues 2nd February 2027 13:00 MCS 3052 and online | |
| Tues 9th February 2027 13:00 MCS 3052 and online | |
| Tues 16th February 2027 13:00 MCS 3052 and online | |
| Tues 23rd February 2027 13:00 MCS 3052 and online | |
| Tues 2nd March 2027 13:00 MCS 3052 and online | |
| Tues 9th March 2027 13:00 MCS 3052 and online | |
| Tues 16th March 2027 13:00 MCS 3052 and online |