3 papers
cs.DS2024
An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
Hitoshi Murakami, Yutaro Yamaguchi
The exact matching problem is a constrained variant of the maximum matching problem: given a graph with each edge having a weight or and an integer , the goal is to find…
cs.DS2023
Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions
Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena +3
We consider the Shortest Odd Path problem, where given an undirected graph , a weight function on its edges, and two vertices and in , the aim is to find an -p…
cs.DS2022
Interval-Memoized Backtracking on ZDDs for Fast Enumeration of All Lower Cost Solutions
Shin-ichi Minato, Mutsunori Banbara, Takashi Horiyama +3
In this paper, we propose a fast method for exactly enumerating a very large number of all lower cost solutions for various combinatorial problems. Our method is based on backtrack…