Experimental Analysis of Treewidth
Experimental Analysis of Treewidth
复制标题
树宽实验分析
DOI：
10.1007/978-3-030-42071-0_15
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hisao Tamaki
中科院分区：
文献类型：
--
作者：
Gima Tatsuya;Hanaka Tesshu;Kiyomi Masashi;Kobayashi Yasuaki;Otachi Yota;Hisao Tamaki
本章的目标是提供从实验中获得的树宽的见解。在我们的实验中，我们统计了随机图实例中与树宽密切相关的组合对象的数量。这些组合对象包括连通集、最小分离子、潜在最大团以及具有某些约束的组合对象。这些实验分析可以补充理论分析，揭示某些算法在实际应用中表现良好而某些算法表现不佳的原因，并为设计新的算法提供依据。
The goal of this chapter is to provide insights into treewidth obtained from experiments. In our experiments, we count the numbers of combinatorial objects closely related to treewidth in random graph instances. These combinatorial objects include connected sets, minimal separators, potential maximal cliques, and those with certain constraints. Such experimental analysis is expected to complement theoretical analysis, reveal the reasons why some algorithms work well in practice while some do not, and provide a basis for designing new algorithms.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
International Symposium on Parameterized and Exact Computation
影响因子：
--
作者：
Holger Dell;T. Husfeldt;B. Jansen;P. Kaski;Christian Komusiewicz;Frances A. Rosamond
通讯作者：
Frances A. Rosamond
影响因子：
1.1
作者：
F. Fomin;Yngve Villanger
通讯作者：
Yngve Villanger
通过最小分隔符的精确和启发式列表计算树宽
DOI：
10.1007/978-3-030-34029-2_15
发表时间：
2019
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
Ryota Kawasumi;Koujin Takeda;HIsao Tamaki
通讯作者：
HIsao Tamaki
影响因子：
1
作者：
Tamaki, Hisao
通讯作者：
Tamaki, Hisao