8 papers
A Parameterized-Complexity Framework for Finding Local Optima
Robert Ganian, Hung P. Hoang, Christian Komusiewicz +1
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood.…
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…
Minimum maximal matchings in permutahedra
Sofia Brenner, Jiří Fink, Hung. P. Hoang +2
We prove that the minimal size of a maximal matching in the permutahedron is asymptotically . On the one hand, we obtain a lower bound $M(π_n) \ge n! (n-1) / (…
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…
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…
Drawings of Complete Multipartite Graphs Up to Triangle Flips
Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang +5
For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended r…
On approximating the rank of graph divisors
Kristóf Bérczi, Hung P. Hoang, Lilla Tóthmérész
Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theor…
Conflict-Free Coloring: Graphs of Bounded Clique Width and Intersection Graphs
Sriram Bhyravarapu, Tim A. Hartmann, Hung P. Hoang +2
A conflict-free coloring of a graph is a (partial) coloring of its vertices such that every vertex has a neighbor whose assigned color is unique in the neighborhood of .…