On the tree-depth and tree-width in heterogeneous random graphs

DOI10.3792/pjaa.98.015OpenAlexW4308117500MaRDI QIDQ2102520

Yilun Shang

Publication date: 29 November 2022

Published in: Proceedings of the Japan Academy. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3792/pjaa.98.015

zbMATH Keywords

random graphtree-widthtree-depthheterogeneous graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stochastic network models in operations research (90B15) Combinatorial probability (60C05) Characterization and structure theory of statistical distributions (62E10)

Related Items (2)

Matrix-scaled resilient consensus of discrete-time and continuous-time networks ⋮ Long paths in heterogeneous random subgraphs of graphs with large minimum degree

Uses Software

• CSparse

Cites Work

• Unnamed Item
• Forbidden graphs for tree-depth
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Treewidth. Computations and approximations
• A note on the majority dynamics in inhomogeneous random graphs
• Structurally parameterized \(d\)-scattered set
• Positive-instance driven dynamic programming for treewidth
• On the tree-depth of random graphs
• Rank-width of random graphs
• Introduction to Random Graphs
• Parameters Tied to Treewidth
• The Role of Elimination Trees in Sparse Factorization
• Treewidth: Characterizations, Applications, and Computations
• Graph minors. II. Algorithmic aspects of tree-width
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Networks
• Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
• Planarity and Genus of Sparse Random Bipartite Graphs
• Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs
• A Note on Treewidth in Random Graphs
• On the treewidth of random geometric graphs and percolated grids
• On Treewidth and Related Parameters of Random Geometric Graphs
• A survey of direct methods for sparse linear systems

This page was built for publication: On the tree-depth and tree-width in heterogeneous random graphs