18 citations · 72 across the 24 of their papers we have counts for
37 papers
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…
Recognising permuted Demidenko matrices
Eranda Çela, Vladimir Deineko, Gerhard J. Woeginger
We solve the recognition problem (RP) for the class of Demidenko matrices. Our result closes a remarkable gap in the recognition of specially structured matrices. Indeed, the recog…
The bipartite travelling salesman problem: A pyramidally solvable case
Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger
In the bipartite travelling salesman problem (BTSP), we are given cities along with an distance matrix and a partition of the cities into red and blue ci…
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…