d棵树的笛卡尔乘积图的双宽度研究
The Twin-Width Study of a Cartesian Product Graph of d Trees
摘要: 在2020年Bonnet，Kim，Thomassé和Watrigant提出了双宽度。本文主要给出了对于任意正整数
d，
d棵树的笛卡尔积乘积图的双宽度的一个上界。
Abstract:
In 2020, Bonnet, Kim, Thomassé, and Watrigant proposed twin-width. This article mainly gave that for any positive integer d, an upper bound on the twin-width of the Cartesian product graph of d trees.
参考文献
|
[1]
|
Bonnet, É., Kim, E.J., Thomassé, S. and Watrigant, R. (2020) Twin-Width I: Tractable FO Model Checking. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Durham, NC, 16-19 November 2020, 601-612. [Google Scholar] [CrossRef]
|
|
[2]
|
Bonnet, É., Geniet, C., Kim, E.J., Thomassé, S. and Watrigant, R. (2021) Twin-Width II: Small Classes. In: Marx, D., Ed., Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1977-1996. [Google Scholar] [CrossRef]
|
|
[3]
|
Pettersson, W. and Sylvester, J. (2022) Bounds on the Twin-Width of Product Graph. arXiv:2202.11556,2022 [Google Scholar] [CrossRef]
|