11 citations · 35 across the 50 of their papers we have counts for
9 papers · 1 filter
Participatory Budgeting with Project Groups
Pallavi Jain, Krzysztof Sornat, Nimrod Talmon +1
We study a generalization of the standard approval-based model of participatory budgeting (PB), in which voters are providing approval ballots over a set of predefined projects and…
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
In the Disjoint Paths problem, the input consists of an -vertex graph and a collection of vertex pairs, , and the objective is to determine whethe…
Approximate Search for Known Gene Clusters in New Genomes Using PQ-Trees
G. R. Zimerman, D. Svetlitsky, M. Zehavi +1
We define a new problem in comparative genomics, denoted PQ-Tree Search, that takes as input a PQ-tree representing the known gene orders of a gene cluster of interest, a gene-…
On the (Parameterized) Complexity of Almost Stable Marriage
Sushmita Gupta, Pallavi Jain, Sanjukta Roy +2
In the Stable Marriage problem. when the preference lists are complete, all agents of the smaller side can be matched. However, this need not be true when preference lists are inco…
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin +2
We prove that the Hadwiger number of an -vertex graph (the maximum size of a clique minor in ) cannot be computed in time , unless the Exponential Time Hypothes…
Parameterized Study of Steiner Tree on Unit Disk Graphs
Sujoy Bhore, Paz Carmi, Sudeshna Kolay +1
We study the Steiner Tree problem on unit disk graphs. Given a vertex unit disk graph , a subset of vertices and a positive integer , the objective…
Parameterized Analysis of Assignment Under Multiple Preferences
Barak Steindl, Meirav Zehavi
The Assignment problem is a fundamental and well-studied problem in the intersection of Social Choice, Computational Economics and Discrete Allocation. In the Assignment problem, a…
The Parameterized Complexity of Guarding Almost Convex Polygons
Akanksha Agrawal, Kristine V. K. Knudsen, Daniel Lokshtanov +2
Art Gallery is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an int…
ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +2
We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time . Under the Exponential Time Hypot…