121 citations · 360 across the 111 of their papers we have counts for
6 papers · 1 filter
Faster Algorithms for Finding and Counting Subgraphs
Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman +2
In this paper we study a natural generalization of both {\sc -Path} and {\sc -Tree} problems, namely, the {\sc Subgraph Isomorphism} problem. In the {\sc Subgraph Isomorphism…
FPT Algorithms for Connected Feedback Vertex Set
Neeldhara Misra, Geevarghese Philip, Venkatesh Raman +2
We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedba…
A Linear Vertex Kernel for Maximum Internal Spanning Tree
Fedor V. Fomin, Serge Gaspers, Saket Saurabh +1
We present a polynomial time algorithm that for any graph G and integer k >= 0, either finds a spanning tree with at least k internal vertices, or outputs a new graph G' on at most…
Kernels for Feedback Arc Set In Tournaments
Stéphane Bessy, Fedor V. Fomin, Serge Gaspers +4
A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Fe…
(Meta) Kernelization
Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov +3
In a parameterized problem, every instance I comes with a positive integer k. The problem is said to admit a polynomial kernel if, in polynomial time, one can reduce the size of th…
Algorithm for Finding -Vertex Out-trees and its Application to -Internal Out-branching Problem
Nathann Cohen, Fedor V. Fomin, Gregory Gutin +3
An out-tree is an oriented tree with only one vertex of in-degree zero. A vertex of is internal if its out-degree is positive. We design randomized and deterministic al…