Großteils kleingeistig
Welcome! I’m Manuel Sorge, researcher in theoretical computer science. News and ramblings:
-
Parameter hierarchy now with database and interactive visualization
Parameters ·I always dreamt to lower the barrier to contributing to the parameter hierarchy and to have a nice interactive visualization. I think I made some significant steps with a new visualization, a human-readable database, and contribution features.
-
Structural sparsity, admissibility, computing short path packings
Algorithms ·Two-sentence summary: I describe a (k · ℓ²)^(k · ℓ) · n^(O(1))-time search-tree algorithm for deciding whether there is a packing of k paths of length at most ℓ in a graph with n vertices. I explain how this problem is motivated by structural sparsity.
-
Three open problems related to temporal graphs
Open problems ·Here are three open problems with relations to temporal graphs that I find interesting. I mentioned them at a recent Dagstuhl Seminar (and I fixed a couple of small errors below). Self-preserving communities In their recent work Krakauer et al. [10] put forward a definition of what a biological individual is, based on information-theoretic measures. Essentially, they propose that individuals...
-
Golomb rulers and algorithmics of structural graph parameters
Paper summaries ·One sentence summary: A cool mathematical structure called Golomb ruler (or Sidon set) can help when designing hardness reductions for structural graph parameters. In this paper [4] we studied a routing problem where we want to route vehicles through a graph such that their routes meet in as few edges as possible. My highlight of the paper is the hardness...