7 citations · 20 across the 13 of their papers we have counts for
14 papers
Solving Routing Problems via Important Cuts
Bin Sheng, Gregory Gutin
We introduce a novel approach of using important cuts which allowed us to design significantly faster fixed-parameter tractable (FPT) algorithms for the following routing problems:…
Solving the r-pseudoforest Deletion Problem in Time Independent of r
Bin Sheng
The feedback vertex set problem is one of the most studied parameterized problems. Several generalizations of the problem have been studied where one is to delete vertices to obtai…
The Paired Domination Number of Cubic Graphs
Bin Sheng, Changhong Lu
Let G be a simple undirected graph with no isolated vertex. A paired dominating set of G is a dominating set which induces a subgraph that has a perfect matching. The paired domina…
FPT algorithms for generalized feedback vertex set problems
Bin Sheng
An r-pseudoforest is a graph in which each component can be made into a forest by deleting at most r edges, and a d-quasi-forest is a graph in which each component can be made into…
The Euler and Chinese Postman Problems on 2-Arc-Colored Digraphs
Bin Sheng, Ruijuan Li, Gregory Gutin
The famous Chinese Postman Problem (CPP) is polynomial time solvable on both undirected and directed graphs. Gutin et al. [Discrete Applied Math 217 (2016)] generalized these resul…
An improved kernel for the cycle contraction problem
Bin Sheng, Yuefang Sun
The problem of modifying a given graph to satisfy certain properties has been one of the central topics in parameterized tractability study. In this paper, we study the cycle contr…