BazTech - Yadda

Ograniczanie wyników

2 Prace Naukowe Politechniki Warszawskiej. Elektronika

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: alfa-klika

Sortuj według:

Ogranicz wyniki do:

Evolutionary approach to solve hub-and-spoke problem using α-cliques

Mażbic-Kulma B., Potrzebowski H., Stańczak J., Sęp K.

Prace Naukowe Politechniki Warszawskiej. Elektronika

2008

z. 165

121-130

The theory of transportation systems deals with models of phenomena connected with movement of goods and persons. The model of the transportation system should simulate a real system, but should also be a tool that enables to solve given transportation tasks. In order to describe transportation system (rail, bus or air), as a routine a connection graph would be used. Vertices of the graph can be train stations, bus stops or in case of air transport - airports. The edges of the graph show direct connections between vertices. It can be noticed that such a graph can have many vertices as well as many edges. Its direct application can be difficult and computational problems can occur while one would try to organize or optimize such a transportation system. Therefore, a method of aggregation of such a graph was introduced, using the hub-and-spoke structured graph of connections. This structure enables to concentrate and order the transport of goods/persons among vertices. To obtain the hub-and-spoke structure an evolutionary algorithm (EA) was applied. EA divides the connection graph into α-cliques (a generalization of the notion of a clique, which groups into sub-graphs highly connected vertices) and then in each α-clique a vertex with a maximum degree in this sub-graph and a maximal number of connections among other selected hubs is chosen. The α-clique with chosen vertex constitutes a "hub" with point-to-point connections - "spokes". This method enables reducing the number of analyzed vertices as well as arcs of the graph. Examples visualizing functioning of the described algorithms are presented later in this paper.

Evolutionary algorithm to find graph covering subsets using α-cliques

Potrzebowski H., Stańczak J., Sęp K.

Prace Naukowe Politechniki Warszawskiej. Elektronika

2006

z. 156

351-358

The article describes a new evolutionary based method to divide graph into strongly connected structures we called α-cliques. The α-clique is a generalization of a clique concept with the introduction of parameter a. Using this parameter it is possible to control the degree (or strength) of connections among vertices (nodes) of this sub-graph structure. The evolutionary approach is proposed as a method that enables to find separate a-cliques that cover the set of graph vertices.