Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs

DOI10.1016/j.dam.2011.10.013zbMath1239.05166OpenAlexW2080300451MaRDI QIDQ412366

Yong Gao

Publication date: 4 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.013

zbMATH Keywords

random graphstreewidthrandom intersection graphsscale-free random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Related Items (14)

Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Computational social choice for coordination in agent networks ⋮ Universality for critical heavy-tailed network models: metric structure of maximal components ⋮ Fractional Edge Cover Number of Model RB ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ On the number of labeled graphs of bounded treewidth ⋮ On giant components and treewidth in the layers model ⋮ Randomized rumor spreading in poorly connected small-world networks ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial) ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ Tree decompositions and social graphs ⋮ Large hypertree width for sparse random hypergraphs ⋮ On the tree-depth and tree-width in heterogeneous random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• On the satisfiability threshold of formulas with three literals per clause
• On tree width, bramble size, and expansion
• The degree sequence of a scale-free random graph process
• Rank-width of random graphs
• The mixing time of the giant component of a random graph
• Statistical mechanics of complex networks
• On the Threshold of Having a Linear Treewidth in Random Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Approximating the unsatisfiability threshold of random formulas
• On Random Intersection Graphs: The Subgraph Problem
• Sharp thresholds of graph properties, and the $k$-sat problem
• Paths in graphs
• Coloring Random Intersection Graphs and Complex Networks

This page was built for publication: Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs