3 citations · 6 across the 11 of their papers we have counts for
Showing 2019Show all
2 papers · 1 filter
cs.DS2019
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…
cs.GT2019
Strategy-Proof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists
Koki Hamada, Shuichi Miyazaki, Hiroki Yanagisawa
In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the well-known stable mechanisms is the man-oriented Gal…