3 papers
cs.DS2025
Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
The starting point of our work is a decade-old open question concerning the subexponential parameterized complexity of \textsc{2-Layer Crossing Minimization}. In this problem, the…
cs.DS2025
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar +1
In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can…
cs.DM2025
Multivariate Exploration of Metric Dilation
Aritra Banik, Fedor V. Fomin, Petr A. Golovach +3
Let be a weighted graph embedded in a metric space . The vertices of correspond to the points in , with the weight of each edge being the distance $d_M…