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

DOI10.3792/PJAA.98.015MaRDI QIDQ2102520zbMATH OpenOpenAlexFDO

Authors 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

heterogeneous graphrandom graphtree-depthtree-width

Mathematics Subject Classification ID

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

Recommendations

• On the tree-depth of random graphs
• On the treewidth and related parameters of random geometric graphs
• A note on treewidth in random graphs
• Tree and forest weights and their application to nonuniform random graphs
• Rank-width of random graphs

Cites work

• A note on the majority dynamics in inhomogeneous random graphs
• A note on treewidth in random graphs
• A survey of direct methods for sparse linear systems
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs
• Forbidden graphs for tree-depth
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3746322 (Why is no real title available?)
• Introduction to Random Graphs
• Networks
• On the tree-depth of random graphs
• On the treewidth of random geometric graphs and percolated grids
• On treewidth and related parameters of random geometric graphs
• Parameters tied to treewidth
• Planarity and genus of sparse random bipartite graphs
• Positive-instance driven dynamic programming for treewidth
• Rank-width of random graphs
• Structurally parameterized \(d\)-scattered set
• The Role of Elimination Trees in Sparse Factorization
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• Treewidth. Computations and approximations
• Treewidth: Characterizations, Applications, and Computations

Cited in

(2)

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

Describes a project that uses

Uses Software

• CSparse

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2102520)