39 citations · 105 across the 10 of their papers we have counts for
4 papers · 1 filter
Bounded Search Tree Algorithms for Parameterized Cograph Deletion: Efficient Branching Rules by Exploiting Structures of Special Graph Classes
James Nastos, Yong Gao
Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingl…
A note on the hardness of graph diameter augmentation problems
James Nastos, Yong Gao
A graph has \emph{diameter} D if every pair of vertices are connected by a path of at most D edges. The Diameter-D Augmentation problem asks how to add the a number of edges to a g…
Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs
Yong Gao
We prove that the treewidth of an Erdös-Rényi random graph $\rg{n, m}$ is, with high probability, greater than for some constant if the edge/vertex ratio …
The Degree Distribution of Random k-Trees
Yong Gao
A power law degree distribution is established for a graph evolution model based on the graph class of k-trees. This k-tree-based graph process can be viewed as an idealized model…