1 citations · 3 across the 12 of their papers we have counts for
7 papers · 1 filter
On Finding -th Smallest Perfect Matchings
Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner +1
Given an undirected weighted graph and an integer , Exact-Weight Perfect Matching (EWPM) is the problem of finding a perfect matching of weight exactly in . In this p…
An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs
Anita Dürr, Nicolas El Maalouly, Lasse Wulf
In 1982 Papadimitriou and Yannakakis introduced the Exact Matching problem, in which given a red and blue edge-colored graph and an integer one has to decide whether there…
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…
Exact Matching and the Top-k Perfect Matching Problem
Nicolas El Maalouly, Lasse Wulf
The aim of this note is to provide a reduction of the Exact Matching problem to the Top- Perfect Matching Problem. Together with earlier work by El Maalouly, this shows that the…
Exact Matching: Correct Parity and FPT Parameterized by Independence Number
Nicolas {El Maalouly}, Raphael Steiner, Lasse Wulf
Given an integer and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly…
On the Recoverable Traveling Salesman Problem
Marc Goerigk, Stefan Lendl, Lasse Wulf
In this paper we consider the Recoverable Traveling Salesman Problem (TSP). Here the task is to find two tours simultaneously, such that the intersection between the tours is at le…
Assistance and Interdiction Problems on Interval Graphs
Hung P. Hoang, Stefan Lendl, Lasse Wulf
We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of origina…