Minimum cost 2-edge-connected Steiner graphs in rectilinear space: an evolutionary approach

Author

Kulturel-Konak, Sadan ; Konak, Abdullah ; Smith, Alice E.

Author_Institution

Dept. of Ind. & Syst. Eng., Auburn Univ., AL, USA

Volume

1

fYear

2000

fDate

2000

Firstpage

97

Abstract

This paper proposes an evolutionary approach for constructing 2-edge-connected minimal Steiner graphs spanning n points given in the rectilinear plane. The 1-edge-connected version of this problem is known as the rectilinear Steiner tree problem and has been widely studied. Despite the possible application areas, the 2-edge-connected problem has not received the same attention. In this paper, some properties of an optimal solution to the problem are used to develop an encoding scheme. The proposed evolutionary approach is compared on a test problem with the optimal TSP tour of the given points

Keywords

evolutionary computation; graph theory; encoding scheme; evolutionary approach; minimum cost 2-edge-connected Steiner graphs; optimal TSP tour; optimal solution; rectilinear plane; rectilinear space; Costs; Encoding; Integrated circuit interconnections; Steiner trees; Surface-mount technology; Systems engineering and theory; Telecommunications; Testing; Topology; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Evolutionary Computation, 2000. Proceedings of the 2000 Congress on

Conference_Location

La Jolla, CA

Print_ISBN

0-7803-6375-2

Type

conf

DOI

10.1109/CEC.2000.870281

Filename

870281