4 citations · 7 across the 6 of their papers we have counts for
6 papers
Lower Bounds for the Domination Numbers of Connected Graphs without Short Cycles
Yinglei Song
In this paper, we obtain lower bounds for the domination numbers of connected graphs with girth at least . We show that the domination number of a connected graph with girth at…
On the Dominating Set Problem in Random Graphs
Yinglei Song
In this paper, we study the {\sc Dominating Set} problem in random graphs. In a random graph, each pair of vertices are joined by an edge with a probability of , where is a…
Time and Space Efficient Algorithms for RNA Folding with the Four-Russians Technique
Yinglei Song
In this paper, we develop new algorithms for the basic RNA folding problem. Given an RNA sequence that contains nucleotides, the goal of the problem is to compute a pseudoknot-…
On the Induced Matching Problem in Hamiltonian Bipartite Graphs
Yinglei Song
In this paper, we study the parameterized complexity and inapproximability of the {\sc Induced Matching} problem in hamiltonian bipartite graphs. We show that, given a hamiltonian…
On the Independent Set and Common Subgraph Problems in Random Graphs
Yinglei Song
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph , each pair of vertices are join…
An Improved Parameterized Algorithm for the Independent Feedback Vertex Set Problem
Yinglei Song
In this paper, we develop a new parameterized algorithm for the {\sc Independent Feedback Vertex Set} (IFVS) problem. Given a graph , the goal of the problem is to determi…