32 citations · 40 across the 3 of their papers we have counts for
4 papers · 1 filter
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…
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…
On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
Yoichi Iwata, Tomoaki Ogasawara, Naoto Ohsaka
There are many classical problems in P whose time complexities have not been improved over the past decades. Recent studies of "Hardness in P" have revealed that, for several of su…
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Takuya Akiba, Yoichi Iwata, Yuichi Yoshida
We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search f…