11 citations · 35 across the 50 of their papers we have counts for
9 papers · 1 filter
Adaptive Manipulation for Coalitions in Knockout Tournaments
Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
Knockout tournaments, also known as single-elimination or cup tournaments, are a popular form of sports competitions. In the standard probabilistic setting, for each pairing of pla…
Parameterized Geometric Graph Modification with Disk Scaling
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph and an integer $k\in\mathb…
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh +2
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colo…
Exact Algorithms for Clustered Planarity with Linear Saturators
Giordano Da Lozzo, Robert Ganian, Siddharth Gupta +3
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an -vertex planar graph whose vertices are partitioned into independent sets (called clus…
A Polynomial Kernel for Deletion to the Scattered Class of Cliques and Trees
Ashwin Jacob, Diptapriyo Majumdar, Meirav Zehavi
The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of…
Subexponential Parameterized Algorithms for Hitting Subgraphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
For a finite set of graphs, the -Hitting problem aims to compute, for a given graph (taken from some graph class ) of vertices (and…
Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
In a disk graph, every vertex corresponds to a disk in and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an…
Hybrid k-Clustering: Blending k-Median and k-Center
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar +2
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clusetring problem, given a set P of…
Parameterized Analysis of Bribery in Challenge the Champ Tournaments
Juhi Chaudhary, Hendrik Molter, Meirav Zehavi
Challenge the champ tournaments are one of the simplest forms of competition, where a (initially selected) champ is repeatedly challenged by other players. If a player beats the ch…