Browsing by Subject "clique"

Now showing 1 - 3 of 3

Access status: Open Access ,
Application of selected methods of graph theory and combinatorial heuristics to minimising the number of transits nodes in an air network
(AGH University of Science and Technology Press, 2008) Mażbic-Kulma, Barbara; Owsiński, Jan Wojciech; Sęp, Krzysztof
In the paper we present the notion of alpha-clique and some of its properties. Covering with alpha-cliques is a preprocessing method for an air network, described as a graph, in which vertices correspond to airports and edges correspond to air connections. Using the alpha-clique cover we obtain a hypergraph, in which we find the minimum transversal. The set of vertices thus obtained is the sought-for set of transits nodes, called hubs. Using the alpha-clique concept instead of proper cliques we can obtain the solution to the graph covering problem easier.
Access status: Open Access ,
Evolutionary approach to find kernel and shell structure of a connection graph
(AGH University of Science and Technology Press, 2009) Mażbic-Kulma, Barbara; Stańczak, Jarosław; Sęp, Krzysztof; Potrzebowski, Henryk
The theory of logistic transportation systems deals with models of phenomena connected with movement of goods and persons. The developed model of the transportation system is expected to simulate a real system, but also should help us 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 etc.. The edges show direct connections between vertices. 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 graph was introduced, using the general kernel and shell structure and its particular instances: hub-and-spoke and α-clique structured graphs of connections. These structures enable to concentrate and order the transport of goods/persons among vertices. To obtain these desired structures an evolutionary algorithm (EA) was applied. This method enables to reduce the number of analyzed vertices as well as arcs/edges of the graph.
Access status: Open Access ,
Finding structure kernel and shell with predetermined cardinality of kernel set, using evolutionary algorithm
(AGH University of Science and Technology Press, 2010) Mażbic-Kulma, Barbara; Stańczak, Jarosław; Sęp, Krzysztof
The theory of logistic transportation systems deals with models of phenomena connected with movement of goods and persons. The developed model of the transportation system is expected to simulate a real system, but also should help us 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 etc. The edges show direct connections between vertices. 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 graph was introduced, using the general kernel and shell structure and its particular instance the ?-clique structured graphs of connections. In the present approach, we use a predetermined number of communication hubs with the possibility of direct determining which nodes should become hubs or selecting them by the solving method. This structure allows to concentrate and order the transport of goods/persons among vertices and enables to reduce the number of analyzed vertices as well as arcs/edges of the graph. To obtain the desired structure, an evolutionary algorithm (EA) was applied.