11 citations · 35 across the 50 of their papers we have counts for
7 papers · 1 filter
A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation
Roni Zoller, Meirav Zehavi, Michal Ziv-Ukelson
An important goal in microbial computational genomics is to identify crucial events in the evolution of a gene that severely alter the duplication, loss and mobilization patterns o…
A Brief Note on Single Source Fault Tolerant Reachability
Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh +1
Let be a directed graph with vertices and edges, and let be a designated source vertex. We consider the problem of single source reachability (SSR) from $s…
Hitting Topological Minors is FPT
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +2
In the Topological Minor Deletion (TM-Deletion) problem input consists of an undirected graph , a family of undirected graphs and an integer . The task is to deter…
The Parameterized Complexity of Motion Planning for Snake-Like Robots
Siddharth Gupta, Guy Sa'ar, Meirav Zehavi
We study the parameterized complexity of a variant of the classic video game Snake that models real-world problems of motion planning. Given a snake-like robot with an initial posi…
Decomposition of Map Graphs with Applications
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan +2
Bidimensionality is the most common technique to design subexponential-time parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behin…
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov +2
Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, r-rank perturbed graphic matroid M is a…
Going Far From Degeneracy
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov +3
An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erdős and Gallai from 1959, every graph of degeneracy d>1…