121 citations · 360 across the 111 of their papers we have counts for
6 papers · 1 filter
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…
Path Contraction Faster than
Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov +2
A graph is contractible to a graph if there is a set , such that is isomorphic to . Here, is the graph obtained from by contracting all…
When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +2
Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in (), or e…
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…
MaxMin Separation Problems: FPT Algorithms for -Separator and Odd Cycle Transversal
Ajinkya Gaikwad, Hitendra Kumar, Soumen Maity +2
In this paper, we study the parameterized complexity of the MaxMin versions of two fundamental separation problems: Maximum Minimal -Separator and Maximum Minimal Odd Cycle Tra…
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…