SEA 2018

Giuseppe F. Italiano, University of Rome Tor Vergata
TITLE:2-Connectivity in Directed Graphs
ABSTRACT: We survey some recent theoretical and experimental results on 2-edge and 2-vertex connectivity in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has a much richer and more complicated structure. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth first search. In the case of digraphs, however, the very same problems have been much more challenging and have been tackled only recently.

Simon J. Puglisi, University of Helsinki
TITLE: Decompressing Massive Datasets
ABSTRACT: Simple and fast decoding is one of the main advantages of LZ-type text encoding used in many popular file compressors and software systems. However, the standard LZ decoding algorithm - which has not changed for 40 years - makes random accesses to the text and cannot be trivially modified to deal with files whose decompressed size exceeds that of main memory. This talk explores two algorithmic approaches to scaling LZ decoding to massive datasets. One of these approaches constitutes the first external memory algorithms for LZ decoding. We show the I/O complexity of these algorithms is optimal and demonstrate through experiments that they are very fast in practice. The second approach is a suite of algorithms that use working space proportional to the size of the compressed data and that streams their output - avoiding access to it during decoding.

Dorothea Wagner, Karlsruhe Institute of Technology (KIT)
TITLE: The Impact of Route Planning Algorithms in Practice
ABSTRACT: Route planning systems belong to the most frequently used information systems at all. The algorithmic core problem of such systems, is the classical shortest paths problem that can be solved by Dijkstra's algorithm which, however, is too slow for practical scenarios.
Algorithms for route planning in transportation networks have recently undergone a rapid development, leading to methods that are up to several million times faster than Dijkstra’s algorithm. For example, for continent-sized road networks, newly-developed algorithms can answer queries in a few hundred nanoseconds, others can incorporate current traffic information in under a second on a commodity server, and many new applications can now be dealt with efficiently. Accordingly, route planning has become a showpiece of Algorithm Engineering demonstrating the engineering cycle that consists of design, analysis, implementation and experimental evaluation of practicable algorithms.
Recently, new challenges like intermodal route planning, incorporating realtime traffic, journey planning with respect to multiple criteria or energy-aware route planning for electric vehicles came up. In this talk we will discuss such new problems and highlight the impact of route planning algorithms for practical systems.