ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

An algorithm for the enumeration of spanning trees (1986)

Winter, Pawel

Springer

BIT 26 (1986), S. 44-62

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1572-9125

Schlagwort(e): Graph Theory ; Spanning Tree ; Enumeration Algorithm

Quelle: Springer Online Journal Archives 1860-2000

Thema: Mathematik

Notizen: Abstract Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n 2). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF01939361

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer