Heuristic Approaches to the Maximization of the Number of Spanning Trees in Regular Graphs

• Autorzy: Sawionek B. , Wojciechowski J. , Arabas J.
• Języki publikacji: EN

Abstrakty

EN

The paper deals with a fundamental problem arising in the design of optimal network structures - maximization of the number of spanning trees. To make the problem computationally tractable, we consider a class of regular graphs. The problem is solved with the usage of evolutionary and 2-opt algorithms. The problem-specific genetic operators are introduced. Various experiments with different graphs structures have been performed, the results are reported, and the methods compared. Influence of introducing some preliminary knowledge about the problem on the algorithm effectiveness is studied.

Słowa kluczowe

EN

graph theory; regular graphs; evolutionary strategy; all terminal reliability

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2000
• Tom: Vol. 48, nr 4
• Strony: 573--586
• Opis fizyczny: 10 rys., bibliogr. 17 poz.

Twórcy

autor

Sawionek B.

autor

Wojciechowski J.

autor

Arabas J.

• Institute of Radioelectronics, ul. Nowowiejska 15/19, 00-665 Warszawa, Poland (Instytut Radioelektroniki),