24 papers
Ultrametric Violation Distance: Polynomial Kernel and FPT Algorithm
Fedor V. Fomin, Petr A. Golovach, Yash Hiren More
In the Ultrametric Violation Distance problem, we are given a set of distances between points, and the goal is to modify the minimum number of distances so that the resulting s…
An FPT Algorithm for Diverse Minimum s-t Cuts
Krishnan Dehaleesan, Pål Grønås Drange, Fedor V. Fomin +2
We study the problem of finding a family of diverse minimum edge s-t cuts in a directed weighted graph G. Given integers k and d, the task is to decide whether G contains k minimum…
Finding irrelevant vertices in linear time on bounded-genus graphs
Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis +1
The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these probl…
Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
Tian Bai, Fedor V. Fomin, Petr A. Golovach +2
Rank aggregation seeks a representative permutation for a collection of rankings and plays a central role in areas such as social choice, information retrieval, and computational b…
Polynomial Kernels for Spanning Tree with Diversity Requirements
Petr A. Golovach, Diptapriyo Majumdar, Saket Saurabh
Given a connected undirected graph , a spanning tree is a subgraph of such that and is a tree. A collection of spanning trees $T_1,\ldots,T_\ell…
Identification to Subclasses of Chordal Graphs
Petr A. Golovach, Laure Morelle, Daniël Paulusma
An identification of two vertices and in a graph replaces them with a new vertex whose neighborhood is the union of the neighborhoods of and . We study the {\sc ${\c…