40 citations · 190 across the 39 of their papers we have counts for
5 papers · 1 filter
Orienteering (with Time Windows) on Restricted Graph Classes
Kevin Buchin, Mart Hagedoorn, Guangping Li +1
Given a graph with edge costs and vertex profits and given a budget B, the Orienteering Problem asks for a walk of cost at most B of maximum profit. Additionally, each profit may b…
Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs
Erik van den Akker, Kevin Buchin, Klaus-Tycho Foerster
We study the problem of multi-agent online graph exploration, in which a team of k agents has to explore a given graph, starting and ending on the same node. The graph is initially…
Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
Peyman Afshani, Mark De Berg, Kevin Buchin +7
We consider the problem of finding patrol schedules for robots to visit a given set of sites in a metric space. Each robot has the same maximum speed and the goal is to min…
Fine-Grained Complexity Analysis of Two Classic TSP Variants
Mark de Berg, Kevin Buchin, Bart M. P. Jansen +1
We analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity. Our first set of results is motivated by the Bitonic TSP problem: gi…
Compact Flow Diagrams for State Sequences
Kevin Buchin, Maike Buchin, Joachim Gudmundsson +2
We introduce the concept of compactly representing a large number of state sequences, e.g., sequences of activities, as a flow diagram. We argue that the flow diagram representatio…