5 citations · 5 across the 4 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…
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi +4
We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus…
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…