In our highly interdependent world, graph problems are at the algorithmic heart of many computational challenges. One focus of this research area is to explore and harness the ultimate limits of algorithmic techniques for solving hard computational problems, particularly on graphs. Pushing forward the theoretical foundations in this area will allow us to reap the rewards in practice many times over. On the other hand, the hardness of certain computational problems also forms the basis of cryptography as we know it today.
SIAM Journal on Discrete Mathematics From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
SIAM Journal on Computing Distributed Edge Coloring in Time Polylogarithmic in Δ
European Symposium on Algorithms (ESA) Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-η Deletion
European Symposium on Algorithms (ESA) Faster Exponential Algorithms For Multi-Machine Scheduling Problems
European Symposium on Algorithms (ESA) The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
