Großteils kleingeistig
Welcome! I’m Manuel Sorge, researcher in theoretical computer science. News and ramblings:
-
Paper published: Iteratively recognizing core-periphery structure
News ·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 [3], for example, in social networks. The idea is that such networks consist of a densely connected core, and a periphery which...
-
Paper published: Approximate Arc Routing
News ·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...
-
Paper published: Routing with Few Collisions
News ·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...
-
Paper published: Enumerating Temporal Cliques
News ·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...