Gedankensprung
Welcome! I’m Manuel Sorge, researcher in theoretical computer science. News and ramblings:
Welcome! I’m Manuel Sorge, researcher in theoretical computer science. News and ramblings:
One sentence summary: Increasing your importance in Facebook by making new friends is quite hard in theory.
Say you could befriend any k persons on Facebook. Who would you add so that you get the most out of your feed? That seems hard to measure but let’s suppose that your feed gets more useful the more central you are in...
One-sentence summary: Recognizing graph properties can be done efficiently by adding vertices one-by-one, perhaps destroying the property, and then repairing it.
The original motivation of this paper is a problem related to checking for core-periphery structure in graphs [1], for example, in social networks. The idea is that such networks consist of a densely connected core, and a...
One sentence summary: We show how to find approximate solutions for arc routing problems using approximation algorithms for the traveling salesman problem.
A very general problem in arc routing is the Capacitated Arc Routing Problem, where we want to route a fleet of vehicles in an in total shortest possible way so to service a given number of streets in...
One sentence summary: We find the spots in time and space in a network that form bottlenecks when routing vehicles from a start to an end point.
In other words, when vehicles drive from some start to some endpoint it might be that at some point some of them collide. We try to route them in such a way that...