Linking and Cutting Spanning Trees

• Tipo: Artigo em Revista Científica Internacional
• Data: 2018

Autores

Russo, LMS (Autor) Outra; Teixeira, AS (Autor) Outra; Francisco, AP (Autor) Outra

Revista

Título: Algorithms

Vol. 11

Página Final: 53

ISSN: 1999-4893

Editora: MDPI

Indexação

ISI Web of Knowledge - 2 Citações

Scopus - 3 Citações

Outras Informações

ID Authenticus: P-00Q-WXH

DOI: 10.3390/a11040053

Abstract (EN): We consider the problem of uniformly generating a spanning tree for an undirected connected graph. This process is useful for computing statistics, namely for phylogenetic trees. We describe a Markov chain for producing these trees. For cycle graphs, we prove that this approach significantly outperforms existing algorithms. For general graphs, experimental results show that the chain converges quickly. This yields an efficient algorithm due to the use of proper fast data structures. To obtain the mixing time of the chain we describe a coupling, which we analyze for cycle graphs and simulate for other graphs.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 34