8 citations · 25 across the 11 of their papers we have counts for
3 papers · 1 filter
A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds
G. Gutin, E. J. Kim, S. Szeider +1
We introduce a new approach for establishing fixed-parameter tractability of problems parameterized above tight lower bounds. To illustrate the approach we consider three problems…
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…
A Polynomial Kernel For Multicut In Trees
Nicolas Bousquet, Jean Daligault, Stephan Thomasse +1
The MULTICUT IN TREES problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer k, whether there exists a set of k edges cutting all the…