b'Meirav Zehavi'

research

∙ 09/18/2023

How to Make Knockout Tournaments More Popular?

Given a mapping from a set of players to the leaves of a complete binary...

0 Juhi Chaudhary, et al. ∙

research

∙ 08/14/2023

Kernelization for Spreading Points

We consider the following problem about dispersing points. Given a set o...

0 Fedor V. Fomin, et al. ∙

research

∙ 08/11/2023

Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large

We study the parameterized complexity of two classic problems on directe...

0 Ashwin Jacob, et al. ∙

research

∙ 08/11/2023

Lossy Kernelization for (Implicit) Hitting Set Problems

We re-visit the complexity of kernelization for the d-Hitting Set proble...

0 Fedor V. Fomin, et al. ∙

research

∙ 08/04/2023

Kernelization of Counting Problems

We introduce a new framework for the analysis of preprocessing routines ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 08/03/2023

Meta-theorems for Parameterized Streaming Algorithms

The streaming model was introduced to parameterized complexity independe...

0 Daniel Lokshtanov, et al. ∙

research

∙ 07/18/2023

𝒫-matchings Parameterized by Treewidth

A matching is a subset of edges in a graph G that do not share an endpoi...

0 Juhi Chaudhary, et al. ∙

research

∙ 07/13/2023

Planar Disjoint Paths, Treewidth, and Kernels

In the Planar Disjoint Paths problem, one is given an undirected planar ...

0 MIchal Wlodarczyk, et al. ∙

research

∙ 07/11/2023

Parameterized Results on Acyclic Matchings with Implications for Related Problems

A matching M in a graph G is an acyclic matching if the subgraph of G in...

0 Juhi Chaudhary, et al. ∙

research

∙ 07/10/2023

Parameterized Analysis of the Cops and Robber Problem

Pursuit-evasion games have been intensively studied for several decades ...

0 Harmender Gahlawat, et al. ∙

research

∙ 04/26/2023

Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs

We investigate a fundamental vertex-deletion problem called (Induced) Su...

0 Daniel Lokshtanov, et al. ∙

research

∙ 01/25/2023

In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?

A temporal graph has an edge set that may change over discrete time step...

0 Pascal Kunz, et al. ∙

research

∙ 01/15/2023

Long Directed Detours: Reduction to 2-Disjoint Paths

We study an "above guarantee" version of the Longest Path problem in dir...

0 Ashwin Jacob, et al. ∙

research

∙ 11/17/2022

(Re)packing Equal Disks into Rectangle

The problem of packing of equal disks (or circles) into a rectangle is a...

0 Fedor V. Fomin, et al. ∙

research

∙ 11/04/2022

A Framework for Approximation Schemes on Disk Graphs

We initiate a systematic study of approximation schemes for fundamental ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 10/10/2022

Parameterized Approaches to Orthogonal Compaction

Orthogonal graph drawings are used in applications such as UML diagrams,...

0 Walter Didimo, et al. ∙

research

∙ 10/08/2022

A Finite Algorithm for the Realizabilty of a Delaunay Triangulation

The Delaunay graph of a point set P ⊆ℝ^2 is the plane graph with the ver...

0 Akanksha Agrawal, et al. ∙

research

∙ 08/23/2021

The complexity of high-dimensional cuts

Cut problems form one of the most fundamental classes of problems in alg...

0 Ulrich Bauer, et al. ∙

research

∙ 06/30/2021

Grid Recognition: Classical and Parameterized Computational Perspectives

Grid graphs, and, more generally, k× r grid graphs, form one of the most...

0 Siddharth Gupta, et al. ∙

research

∙ 05/21/2021

Verification of Multi-Layered Assignment Problems

The class of assignment problems is a fundamental and well-studied class...

0 Barak Steindl, et al. ∙

research

∙ 03/31/2021

An Exponential Time Parameterized Algorithm for Planar Disjoint Paths

In the Disjoint Paths problem, the input is an undirected graph G on n v...

0 Daniel Lokshtanov, et al. ∙

research

∙ 02/07/2021

Multivariate Analysis of Scheduling Fair Competitions

A fair competition, based on the concept of envy-freeness, is a non-elim...

0 Siddharth Gupta, et al. ∙

research

∙ 12/09/2020

Participatory Budgeting with Project Groups

We study a generalization of the standard approval-based model of partic...

1 Pallavi Jain, et al. ∙

research

∙ 08/19/2020

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths

In the Disjoint Paths problem, the input consists of an n-vertex graph G...

0 Daniel Lokshtanov, et al. ∙

research

∙ 05/17/2020

On the (Parameterized) Complexity of Almost Stable Marriage

In the Stable Marriage problem. when the preference lists are complete, ...

0 Sushmita Gupta, et al. ∙

research

∙ 04/24/2020

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds

We prove that the Hadwiger number of an n-vertex graph G (the maximum si...

0 Fedor V. Fomin, et al. ∙

research

∙ 04/20/2020

Parameterized Study of Steiner Tree on Unit Disk Graphs

We study the Steiner Tree problem on unit disk graphs. Given a n vertex ...

0 Sujoy Bhore, et al. ∙

research

∙ 04/01/2020

Parameterized Analysis of Assignment Under Multiple Preferences

The Assignment problem is a fundamental, well-studied problem in the int...

0 Barak Steindl, et al. ∙

research

∙ 03/17/2020

The Parameterized Complexity of Guarding Almost Convex Polygons

Art Gallery is a fundamental visibility problem in Computational Geometr...

0 Akanksha Agrawal, et al. ∙

research

∙ 03/02/2020

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs

We present an algorithm for the extensively studied Long Path and Long C...

0 Fedor V. Fomin, et al. ∙

research

∙ 12/04/2019

A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation

An important goal in microbial computational genomics is to identify cru...

0 Roni Zoller, et al. ∙

research

∙ 04/17/2019

A Brief Note on Single Source Fault Tolerant Reachability

Let G be a directed graph with n vertices and m edges, and let s ∈ V(G) ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 04/05/2019

Reducing Topological Minor Containment to the Unique Linkage Theorem

In the Topological Minor Containment problem (TMC) problem two undirecte...

0 Fedor V. Fomin, et al. ∙

research

∙ 03/06/2019

The Parameterized Complexity of Motion Planning for Snake-Like Robots

We study the parameterized complexity of a variant of the classic video ...

0 Siddharth Gupta, et al. ∙

research

∙ 03/04/2019

Decomposition of Map Graphs with Applications

Bidimensionality is the most common technique to design subexponential-t...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/19/2019

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals

Perturbed graphic matroids are binary matroids that can be obtained from...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/07/2019

Going Far From Degeneracy

An undirected graph G is d-degenerate if every subgraph of G has a verte...

0 Fedor V. Fomin, et al. ∙

research

∙ 06/24/2018

On r-Simple k-Path and Related Problems Parameterized by k/r

Abasi et al. (2014) and Gabizon et al. (2015) studied the following prob...

0 Gregory Gutin, et al. ∙

research

∙ 03/25/2018

Popular Matching in Roommates Setting is NP-hard

An input to the Popular Matching problem, in the roommates setting, cons...

0 Sushmita Gupta, et al. ∙

research

∙ 02/20/2018

The Parameterized Complexity of Packing Arc-Disjoint Cycles in Tournaments

Given a directed graph D on n vertices and a positive integer k, the Arc...

0 R. Krithika, et al. ∙

research

∙ 02/05/2018

Reducing CMSO Model Checking to Highly Connected Graphs

Given a Counting Monadic Second Order (CMSO) sentence ψ, the CMSO[ψ] pro...

0 Daniel Lokshtanov, et al. ∙

research

∙ 07/17/2017

On Treewidth and Stable Marriage

Stable Marriage is a fundamental problem to both computer science and ec...

0 Sushmita Gupta, et al. ∙

Meirav Zehavi

Featured Co-authors