Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph and a constraint function , we ask for a (minimu…
cs.DS2024
Parameterized Complexity of Efficient Sortation
Robert Ganian, Hung P. Hoang, Simon Wietheger
A crucial challenge arising in the design of large-scale logistical networks is to optimize parcel sortation for routing. We study this problem under the recent graph-theoretic for…
cs.DS2024
The -Opt algorithm for the Traveling Salesman Problem has exponential running time for
Sophia Heimann, Hung P. Hoang, Stefan Hougardy
The -Opt algorithm is a local search algorithm for the Traveling Salesman Problem. Starting with an initial tour, it iteratively replaces at most edges in the tour with the…