Hitting times for arc-disjoint arborescences in random digraph processes

Autor(es)

Collares, Mauricio ; Kohayakawa, Yoshiharu ; Martins, Taisa ; Parente, Roberto ; Souza, Victor ; Ferreira, CE ; Lee, O ; Miyazawa, FK

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 9-pg., 2021-01-01.

Resumo

In this work, we study hitting times for the appearance of a spanning structure in the Erdos-Renyi random directed graph processes. Namely, we are concerned with the appearance of an arborescence, a spanning digraph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v. Let D(n, 0), D(n, 1),..., D(n, n(n 1)) be the random digraph process where for every m is an element of {0,, n(n 1)}, D(n, m) is a digraph with vertex set {1,..., n}; D(n, 0) has no arcs and, for 1 <= m <= n(n 1), the digraph D(n, m) is obtained by adding an arc to D(n, m - 1), chosen uniformly at random among the not present arcs. In this paper we determine the hitting time for the existence of k arc -disjoint arborescences when k = k(n) << root log n (C) 2021 The Authors. Published by Elsevier B.V. (AU)

• Processo FAPESP: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores