8 papers · 1 filter
Integer Programming and Incidence Treedepth
Eduard Eiben, Robert Ganian, Dušan Knop +3
Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matri…
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.}…
Extending Nearly Complete 1-Planar Drawings in Polynomial Time
Eduard Eiben, Robert Ganian, Thekla Hamm +2
The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph , a conne…
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…