A Note on Treewidth in Random Graphs

DOI10.1007/978-3-642-22616-8_38zbMath1342.05145OpenAlexW2114672199MaRDI QIDQ5199174

Chaoyi Wang, Ke Xu, Tian Liu, Peng Cui

Publication date: 12 August 2011

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22616-8_38

Mathematics Subject Classification ID

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

Related Items (9)

Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Complete Boolean satisfiability solving algorithms based on local search ⋮ Fractional Edge Cover Number of Model RB ⋮ On giant components and treewidth in the layers model ⋮ Tree decompositions and social graphs ⋮ Large hypertree width for sparse random hypergraphs ⋮ On the tree-depth and tree-width in heterogeneous random graphs ⋮ New limits of treewidth-based tractability in optimization

This page was built for publication: A Note on Treewidth in Random Graphs