18 citations · 72 across the 24 of their papers we have counts for
13 papers · 1 filter
A linear time algorithm for linearizing quadratic and higher-order shortest path problems
Eranda Çela, Bettina Klinz, Stefan Lendl +2
An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same…
An Investigation of the Recoverable Robust Assignment Problem
Dennis Fischer, Tim A. Hartmann, Stefan Lendl +1
We investigate the so-called recoverable robust assignment problem on balanced bipartite graphs with vertices, a mainstream problem in robust optimization: For two given linea…
Travelling salesman paths on Demidenko matrices
Eranda Cela, Vladimir G. Deineko, Gerhard J. Woeginger
In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his…
Good Things Come to Those Who Swap Objects on Paths
Matthias Bentert, Jiehua Chen, Vincent Froese +1
We study a simple exchange market, introduced by Gourvés, Lesca and Wilczynski (IJCAI-17), where every agent initially holds a single object. The agents have preferences over the o…
Dispersing obnoxious facilities on a graph
Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl +1
We study a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal i…
Graph Similarity and Approximate Isomorphism
Martin Grohe, Gaurav Rattan, Gerhard J. Woeginger
The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not rec…