文章基本信息

标题：On the treewidth and related parameters of random geometric graphs
本地全文：下载
作者：Dieter Mitsche ; Guillem Perarnau
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：408-419
DOI：10.4230/LIPIcs.STACS.2012.408
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G(n,r) in [0,sqrt(n)]^2. More precisely, we show that there exists some c_1 > 0, such that for any constant 0 c_1, such that for any r=r(n)> c_2, tw(G)=Theta(r sqrt(n)). Our proofs show that for the corresponding values of r the same asymptotic bounds also hold for the pathwidth and treedepth of a random geometric graph.
关键词：Random geometric graphs; treewidth; treedepth