25 citations · 109 across the 80 of their papers we have counts for
6 papers · 1 filter
Approximation Schemes for Low-Rank Binary Matrix Approximation Problems
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov +2
We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering p…
On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos
We consider the problems of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the result of the modification satisfies some prop…
Partial complementation of graphs
Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme +1
A partial complement of the graph is a graph obtained from by complementing all the edges in one of its induced subgraphs. We study the following algorithmic question: for…
Clustering to Given Connectivities
Petr A. Golovach, Dimitrios M. Thilikos
We define a general variant of the graph clustering problem where the criterion of density for the clusters is (high) connectivity. In {\sc Clustering to Given Connectivities}, we…
Parameterized Low-Rank Binary Matrix Approximation
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan
We provide a number of algorithmic results for the following family of problems: For a given binary m\times n matrix A and integer k, decide whether there is a "simple" binary matr…
Parameterized Aspects of Strong Subgraph Closure
Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis +2
Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized…