On the Threshold of Having a Linear Treewidth in Random Graphs

DOI10.1007/11809678_25zbMath1162.68451OpenAlexW1490290385MaRDI QIDQ3591317

Yong Gao

Publication date: 10 September 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11809678_25

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Rank-width of random graphs ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ On the tree-depth of random graphs ⋮ Fractional Edge Cover Number of Model RB ⋮ Large hypertree width for sparse random hypergraphs

This page was built for publication: On the Threshold of Having a Linear Treewidth in Random Graphs