Symbolic regression for approximating graph geodetic number

Anaqreh Ahmad T. and G.-Tóth Boglárka and Vinkó Tamás: Symbolic regression for approximating graph geodetic number. In: Acta cybernetica, (25) 2. pp. 151-169. (2021)

[thumbnail of cybernetica_025_numb_002_151-169.pdf] Cikk, tanulmány, mű
cybernetica_025_numb_002_151-169.pdf

Download (258kB)

Abstract

Graph properties are certain attributes that could make the structure of the graph understandable. Occasionally, standard methods cannot work properly for calculating exact values of graph properties due to their huge computational complexity, especially for real-world graphs. In contrast, heuristics and metaheuristics are alternatives proved their ability to provide sufficient solutions in a reasonable time. Although in some cases, even heuristics are not efficient enough, where they need some not easily obtainable global information of the graph. The problem thus should be dealt in completely different way by trying to find features that related to the property and based on these data build a formula which can approximate the graph property. In this work, symbolic regression with an evolutionary algorithm called Cartesian Genetic Programming has been used to derive formulas capable to approximate the graph geodetic number which measures the minimal-cardinality set of vertices, such that all shortest paths between its elements cover every vertex of the graph. Finding the exact value of the geodetic number is known to be NP-hard for general graphs. The obtained formulas are tested on random and real-world graphs. It is demonstrated how various graph properties as training data can lead to diverse formulas with different accuracy. It is also investigated which training data are really related to each property.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2021
Volume: 25
Number: 2
ISSN: 0324-721X
Page Range: pp. 151-169
Language: English
Publisher: University of Szeged, Institute of Informatics
Place of Publication: Szeged
Event Title: Conference of PhD Students in Computer Science (12.) (2020) (Szeged)
Related URLs: http://acta.bibl.u-szeged.hu/75565/
DOI: 10.14232/actacyb.289041
Uncontrolled Keywords: Programozás
Additional Information: Bibliogr.: p. 164-167. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2022. May. 12. 13:39
Last Modified: 2022. May. 12. 13:47
URI: http://acta.bibl.u-szeged.hu/id/eprint/75603

Actions (login required)

View Item View Item