Autor(es)

Ali, Alonso ; Lee, Orlando

• Tipo de documento: Artigo Científico
• Fonte: XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023; v. 224, p. 8-pg., 2023-01-01.

Resumo

Let G be a graph and let r be a fixed vertex of G. Two spanning trees T-1 and T-2 of G rooted at r are edge-independent if for every vertex v is an element of V(G), the paths from v to r in T-1 and from v to r in T-2 are edge-disjoint. Itai and Zehavi conjectured that for every k-edge-connected graph and any vertex r is an element of V(G) there are k edge-independent spanning trees rooted at r (Edge-Independent Spanning Trees Conjecture). Itai and Rodeh proved the case k =2, Schlipf and Schmidt proved the case k = 3, and Hoyer and Thomas proved the case k = 4 of the conjecture. In this paper, we prove the case k = 5. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 20/11118-6 - Conexidade em grafos
• Beneficiário: Alonso Ali Gonçalves
• Modalidade de apoio: Bolsas no Brasil - Doutorado