On the Threshold of Having a Linear Treewidth in Random Graphs

DOI10.1007/11809678_25MaRDI QIDQ3591317zbMATH OpenOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A note on treewidth in random graphs
• Algorithms finding tree-decompositions of graphs
• The algorithmic theory of treewidth
• Computational aspects of treewidth for graph
• scientific article; zbMATH DE number 1944139

Cited in

(11)

• Large hypertree width for sparse random hypergraphs
• On the tree-depth of random graphs
• Rank-width of random graphs
• Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
• scientific article; zbMATH DE number 2013546 (Why is no real title available?)
• Fractional edge cover number of Model RB
• scientific article; zbMATH DE number 4121424 (Why is no real title available?)
• scientific article; zbMATH DE number 7263059 (Why is no real title available?)
• A note on treewidth in random graphs
• An upper bound for the critical probability on the Cartesian product graph of a regular tree and a line
• Graphs of linear growth have bounded treewidth

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

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