ON VERTEX COVER PROBLEM WITH THE UNIQUE PRICE OF VERTICES
Keywords:
biggest degrees, lowest degrees, maximal price, minimal price, neighboring vertex, superfluous vertex, vertex cover, unique priceAbstract
This paper presents algorithm of the heuristic solution of vertex cover with the unique price of vertices. This algorithm consists of two algorithms. The first algorithm scans vertices from a maximal degree decreasingly and compares price of chosen vertex with the sum of prices of neighboring vertices. If the price of chosen vertex is less than or equal to the sum of prices of neighboring vertices than we place this vertex into a optimal solution. In opposite case we place neighboring vertices into the optimal solution. We repeat this process until it is possible with respekt to conditions. The second algorithm segregates superfluous vertices from the optimal set after the first algorithm.
References
GARREY, M.R., JOHNSON, D. Computers and Intractability. A Guide to the Theory of
NP-completes. W.H.Freeman and Co., San Francisco, 1979, pp. 337.
MEDVIĎ, V. Minimalizácia rozmiestňovania kontrolných bodov v komunikačných
sieťach. Zborník 9. medzinárodnej ved. konf., Vysoká škola dopravy a spojov, Strojnícka
fakulta, Žilina 1993.
MEDVIĎ, V. Zovšeobecnená zasiahnutá množina, Acta mathematika 6, Faculty of
Natural sciences, Const. Public., Nitra 2004, 243 – 248 pp.
MEDVIĎ, V. Transcom 2005, 6-th European Conference of Young Research and Science
Workers in Transport and Telecommunications, Žilina 2005, 95 – 98 pp.
Downloads
Published
Issue
Section
License
Copyright (c) 2020 Vladimír Medviď
This work is licensed under a Creative Commons Attribution 4.0 International License.
