9 papers · 1 filter
EPTAS for -means Clustering of Affine Subspaces
Eduard Eiben, Fedor V. Fomin, Petr A. Golovach +3
We consider a generalization of the fundamental -means clustering for data with incomplete or corrupted entries. When data objects are represented by points in , a…
Component Order Connectivity in Directed Graphs
J. Bang-Jensen, E. Eiben, G. Gutin +2
A directed graph is semicomplete if for every pair of vertices of there is at least one arc between and \viol{Thus, a tournament is a semicomplete digraph.}…
A Polynomial Kernel for Line Graph Deletion
Eduard Eiben, William Lochet
The line graph of a graph is the graph whose vertex set is the edge set of and there is an edge between if and share an endpoint in . A grap…
Extending Partial 1-Planar Drawings
Eduard Eiben, Robert Ganian, Thekla Hamm +2
Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph…
Manipulating Districts to Win Elections: Fine-Grained Complexity
Eduard Eiben, Fedor V. Fomin, Fahad Panolan +1
Gerrymandering is a practice of manipulating district boundaries and locations in order to achieve a political advantage for a particular party. Lewenberg, Lev, and Rosenschein [AA…
Removing Connected Obstacles in the Plane is FPT
Eduard Eiben, Daniel Lokshtanov
Given two points in the plane, a set of obstacles defined by closed curves, and an integer , does there exist a path between the two designated points intersecting at most o…