Treewidth computation and extremal combinatorics
Treewidth computation and extremal combinatorics
复制标题
树宽计算和极值组合
DOI：
10.1007/s00493-012-2536-z
复制
发表时间：
2012
期刊：
影响因子：
1.1
通讯作者：
Yngve Villanger
中科院分区：
文献类型：
--
作者：
F. Fomin;Yngve Villanger
对于给定的图G和整数b，f≥0，设G是G的一个顶点的子集，使得由S诱导的G的子图是连通的，并且S可以通过去掉几个顶点与G的其他顶点分开.我们证明了每个顶点上的图至多包含这样的顶点子集。极值组合学的这一结果在几种计数和精确算法的设计中似乎非常有用。特别地，我们利用它给出了一个给定的顶点图G·利用指数空间计算Gin Timeo(1.7549n)的树宽·在Timeo(2.6151n)和多项式空间·在Timeo(N5·)上判定Gin Timeo(1.6181n)的树宽是否最大·列出Gin Timeo(1.6181n)的所有最小分隔符和Gin Timeo(1.7549n)的所有潜在的最大团的算法。
For a given graphGand integersb,f≥0, letSbe a subset of vertices ofGof sizeb+1 such that the subgraph ofGinduced bySis connected andScan be separated from other vertices ofGby removingfvertices. We prove that every graph onnvertices contains at mostsuch vertex subsets. This result from extremal combinatorics appears to be very useful in the design of several enumeration and exact algorithms. In particular, we use it to provide algorithms that for a givenn-vertex graphG•compute the treewidth ofGin timeO(1.7549n) by making use of exponential space and in timeO(2.6151n) and polynomial space•decide in timeO(n5·) if the treewidth ofGis at mostk•list all minimal separators ofGin timeO(1.6181n) and all potential maximal cliques ofGin timeO(1.7549n).This significantly improves previous algorithms for these problems.