GENETIC ALGORITHMS FOR FINDING THE SEMI-OBNOXIOUS (K,L)-CORE OF A GRAPH

Authors

DOI:

https://doi.org/10.23055/ijietap.2020.27.3.3218

Keywords:

Core, Genetic algorithm, Median subtree, Semi-obnoxious

Abstract

In this paper, we consider the network facility location problem and in particular, we investigate the problem of finding the (k,l)-core of a graph. This problem has been considered in recent years since it plays an important role in some practical applications such as transit routes, pipelines, drainage or irrigation ditches. A -core of a given graph , is a subtree of  with at most  end nodes and with a diameter of at most  which the sum of the distances from all vertices to this subtree is minimized. The vertices of the graph are usually considered as the clients and the demand of client on a vertex is considered as the weight of this vertex. The -core is the location of the facilities. In the semi-obnoxious case, the facilities are desirable for a part of clients and undesirable for the rest. The problem of finding the semi-obnoxious -core on general graphs is NP-hard, therefore, we present three genetic algorithms for solving this problem. The numerical experiments were carried out on some standard test problems. Then we compare three algorithms in terms of speed of algorithms and quality of answers.

Author Biography

Jafar Fathali, Shahrood University of Technology

Department of Mathematics

Published

2020-12-19

How to Cite

Motevalli Ashkezari, S., & Fathali, J. (2020). GENETIC ALGORITHMS FOR FINDING THE SEMI-OBNOXIOUS (K,L)-CORE OF A GRAPH. International Journal of Industrial Engineering: Theory, Applications and Practice, 27(3). https://doi.org/10.23055/ijietap.2020.27.3.3218

Issue

Section

Operations Research