5 citations · 6 across the 5 of their papers we have counts for
5 papers
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2
Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest…
A Weighted Linear Matroid Parity Algorithm
Satoru Iwata, Yusuke Kobayashi
The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential…
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set
Yoichi Iwata, Yusuke Kobayashi
Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuris…
An FPT Algorithm for Max-Cut Parameterized by Crossing Number
Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki +1
The Max-Cut problem is known to be NP-hard on general graphs, while it can be solved in polynomial time on planar graphs. In this paper, we present a fixed-parameter tractable algo…
The Perfect Matching Reconfiguration Problem
Marthe Bonamy, Nicolas Bousquet, Marc Heinrich +5
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a fl…