期刊
INFORMATION PROCESSING LETTERS
卷 174, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.ipl.2021.106194
关键词
Bondy-Lovasz lemma; Gyori-Lovasz Theorem; Graph diameter; Graph partitioning; Graph algorithms
资金
- NSF [CCF-0643934, CCF-0729102]
- Korea Foundation for Advanced Studies
- National Research Foundation of Korea (NRF) - Korea government (MSIT) [NRF-2019R1C1C1008934]
- AFOSR [FA9550-09-1-0100]
- Microsoft Research New Faculty Fellowship
- Google Research Grant
- Alfred P. Sloan Foundation Fellowship
We present a strengthened version of a lemma by Bondy and Lovasz, which establishes the connectivity of a graph of spanning trees and proves an asymptotically tight bound on the worst-case diameter.
We present a strengthened version of a lemma due to Bondy and Lovasz. This lemma establishes the connectivity of a certain graph whose nodes correspond to the spanning trees of a 2-vertex-connected graph, and implies the k = 2 case of the Gyori-Lovasz Theorem on partitioning of k-vertex-connected graphs. Our strengthened version constructively proves an asymptotically tight O(vertical bar V vertical bar(2)) bound on the worst-case diameter of this graph of spanning trees. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据