Algorithms for generating all possible spanning trees of a simple undirected connected graph: an extensive review
| Autor: | Rajat Kumar Pal, Sumon Chowdhury, Ranjan Mehera, Maumita Chakraborty, Joymallya Chakraborty |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Graph size
0209 industrial biotechnology Spanning tree Computer science Computational intelligence Graph theory 02 engineering and technology General Medicine 020901 industrial engineering & automation 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 020201 artificial intelligence & image processing Literature survey Algorithm Connectivity MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Complex & Intelligent Systems. 5:265-281 |
| ISSN: | 2198-6053 2199-4536 |
| DOI: | 10.1007/s40747-018-0079-7 |
| Popis: | Generation of all possible spanning trees of a graph is a major area of research in graph theory as the number of spanning trees of a graph increases exponentially with graph size. Several algorithms of varying efficiency have been developed since early 1960s by researchers around the globe. This article is an exhaustive literature survey on these algorithms, assuming the input to be a simple undirected connected graph of finite order, and contains detailed analysis and comparisons in both theoretical and experimental behavior of these algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink