This year's European Symposium of Algorithms (ESA), which we will host ourselves in Potsdam from September 5-9, will feature one paper by our group in Track B. The paper was written by Philipp Fischbeck who visited former group member Thomas Bläsius at his new group at KIT to start the collaboration. In the paper, they evaluate the performance of six graph algorithms on 2751 sparse real-world networks, and compare this to the performance on networks generated from random models. They find that the idealized setting of network models translates well to the real world, and that the two network properties heterogeneity and locality are the core properties impacting the graph algorithm performance.
Additionally, for Approximation Algorithms for Combinatorial Optimization Problems (APPROX) the paper A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs was accpeted. The paper addresses the problem of multicommodity flow and multicut in graphs of treewidth 2. The authors prove bounds for the multiflow multicut gap that improve on the best known bounds for such graphs to date. Their algorithm is fully combinatorial and builds on the primal-dual algorithm of Garg, Vazirani, and Yannakakis for multicut in trees and the augmenting paths framework of Ford and Fulkerson.
