Welcome
Manuel Sorge, researcher in theoretical computer science. News and miscellanous ramblings:
Manuel Sorge, researcher in theoretical computer science. News and miscellanous ramblings:
Clustering data is a basic task and has gotten immense attention, in particular graph-based clustering, where we are given pairwise relationships between people, say, and we want to group them into well-connected clusters with fewer connections between clusters.
Here is an interesting relatively new twist on this kind of problem [1]: Instead of static data, like in a snapshot...
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 periphery...
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...
One sentence summary: Find all regular meetings in time stamped message data.
Slightly more precise: Given a set of time stamped bilateral messages between persons, enumerate all combinations of a time frame T and a set S of persons such that each pair of persons in S communicate regularly during the time frame T.
Message data between individuals nowadays is...
Hope you enjoy the new website. It is made with Jekyll, a static website generator, by modifying David Darnes’ Garth theme. The bibliography is generated from bibtex using Sylvester Keil’s jekyll-scholar plugin. Special thanks to Pascal Poizat for explaining a similar setup.