8 citations · 25 across the 11 of their papers we have counts for
5 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…
FPT Algorithms and Kernels for the Directed -Leaf Problem
Jean Daligault, Gregory Gutin, Eun Jung Kim +1
A subgraph of a digraph is an {\em out-branching} if is an oriented spanning tree with only one vertex of in-degree zero (called the {\em root}). The vertices of of…
Fixed-Parameter Complexity of Minimum Profile Problems
Gregory Gutin, Stefan Szeider, Anders Yeo
Let be a graph. An ordering of is a bijection $α: V\dom \{1,2,..., |V|\}.$ For a vertex in , its closed neighborhood is T…
The Linear Arrangement Problem Parameterized Above Guaranteed Value
G. Gutin, A. Rafiey, S. Szeider +1
A linear arrangement (LA) is an assignment of distinct integers to the vertices of a graph. The cost of an LA is the sum of lengths of the edges of the graph, where the length of a…