49 citations · 80 across the 23 of their papers we have counts for
10 papers · 1 filter
Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles
Yusuke Kobayashi
The weighted -free -matching problem is the following problem: given an undirected graph , a weight function on its edge set, and a set of triangle…
Linear-Time Recognition of Double-Threshold Graphs
Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi +1
A graph is a double-threshold graph if there exist a vertex-weight function and two real numbers s…
Parameterized Algorithms for Maximum Cut with Connectivity Constraints
Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi +1
We study two variants of \textsc{Maximum Cut}, which we call \textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted…
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…