Großteils kleingeistig
Welcome! I’m Manuel Sorge, researcher in theoretical computer science. News and ramblings:
-
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...
-
10001
Chinese ·Since in Chinese vocabulary you have both the sound and the elaborate characters, it can happen that the characters transmit some meaning which otherwise could get lost. My current favorite example is 万一 (wan4yi1), which can mean “in case”, “random event”, “emergency”, “eventuality” and the two characters are literally just a number: 10001. For example, you can say 为什么你带雨伞？ (why...