14 citations · 22 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
A Turing Kernelization Dichotomy for Structural Parameterizations of -Minor-Free Deletion
Huib Donkers, Bart M. P. Jansen
For a fixed finite family of graphs , the -Minor-Free Deletion problem takes as input a graph and an integer and asks whether there exists a se…
cs.DS2019
Hamiltonicity below Dirac's condition
Bart M. P. Jansen, László Kozma, Jesper Nederlof
Dirac's theorem (1952) is a classical result of graph theory, stating that an -vertex graph () is Hamiltonian if every vertex has degree at least . Both the value…