Heuristic maximization of the number of spanning trees in regular graphs |
| |
| Authors: | Jacek Wojciechowski Jaros?aw Arabas |
| |
| Institution: | a Institute of Radiolelectronics, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland
b Institute of Electronic Systems, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland |
| |
| Abstract: | This paper deals with the problem of finding graphs (directed and undirected) maximizing the number of spanning trees among the regular graphs with the same number of nodes and edges. The approach is based on heuristic algorithms such as k-optimal and evolutionary. The emphasis is rather on checking whether these techniques are applicable to solving extremal graph problems than investigating generic structures of optimal graphs. For this reason circulant graphs, for which computationally effective tree counting formulas exist, are discussed first and then the results extended to cover the class of regular graphs. |
| |
| Keywords: | t-Optimal graph Regular graphs Spanning tree Discrete optimization Evolutionary algorithm 2-Optimal algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
