32 citations · 56 across the 11 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.DS2019
Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen +1
Local search is a widely-employed strategy for finding good solutions to Traveling Salesman Problem. We analyze the problem of determining whether the weight of a given cycle can b…
cs.DS2019
Finding a Shortest Non-zero Path in Group-Labeled Graphs
Yoichi Iwata, Yutaro Yamaguchi
We study a constrained shortest path problem in group-labeled graphs with nonnegative edge length, called the shortest non-zero path problem. Depending on the group in question, th…
cs.DS2019★ 5 cited
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…