Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
From MaRDI portal
Publication:412366
DOI10.1016/J.DAM.2011.10.013zbMATH Open1239.05166OpenAlexW2080300451MaRDI QIDQ412366FDOQ412366
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
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Statistical mechanics of complex networks
- On Random Intersection Graphs: The Subgraph Problem
- A partial k-arboretum of graphs with bounded treewidth
- The degree sequence of a scale-free random graph process
- Paths in graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Treewidth. Computations and approximations
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- Coloring Random Intersection Graphs and Complex Networks
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- On the satisfiability threshold of formulas with three literals per clause
- On tree width, bramble size, and expansion
- Rank-width of random graphs
- The mixing time of the giant component of a random graph
- On the Threshold of Having a Linear Treewidth in Random Graphs
Cited In (15)
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial)
- On the tree-depth and tree-width in heterogeneous random graphs
- Universality for critical heavy-tailed network models: metric structure of maximal components
- First-Order Model-Checking in Random Graphs and Complex Networks
- Randomized rumor spreading in poorly connected small-world networks
- Fractional Edge Cover Number of Model RB
- Large hypertree width for sparse random hypergraphs
- Computational social choice for coordination in agent networks
- Deleting edges to restrict the size of an epidemic: a new application for treewidth
- On giant components and treewidth in the layers model
- On the number of labeled graphs of bounded treewidth
- An Experimental Study of the Treewidth of Real-World Graph Data
- On the treewidth of random geometric graphs and percolated grids
- Tree decompositions and social graphs
- Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
This page was built for publication: Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412366)
