39 citations · 105 across the 10 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.DM2009
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…
cs.DM2009★ 3 cited
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 …