DC FieldValueLanguage
dc.contributor.authorKratica, Jozefen
dc.contributor.authorČangalović, Mirjanaen
dc.contributor.authorKovačević-Vujčić, Veraen
dc.date.accessioned2020-04-26T19:14:55Z-
dc.date.available2020-04-26T19:14:55Z-
dc.date.issued2009-07-01en
dc.identifier.issn0305-0548en
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/498-
dc.description.abstractIn this paper we consider the minimal doubly resolving sets problem (MDRSP) of graphs. We prove that the problem is NP-hard and give its integer linear programming formulation. The problem is solved by a genetic algorithm (GA) that uses binary encoding and standard genetic operators adapted to the problem. Experimental results include three sets of ORLIB test instances: crew scheduling, pseudo-boolean and graph coloring. GA is also tested on theoretically challenging large-scale instances of hypercubes and Hamming graphs. Optimality of GA solutions on smaller size instances has been verified by total enumeration. For several larger instances optimality follows from the existing theoretical results. The GA results for MDRSP of hypercubes are used by a dynamic programming approach to obtain upper bounds for the metric dimension of large hypercubes up to 290 nodes, that cannot be directly handled by the computer.en
dc.publisherElsevier-
dc.relationSerbian Ministry of Science, Grant no. 144015G-
dc.relation.ispartofComputers and Operations Researchen
dc.subjectEvolutionary approach | Genetic algorithms | Hypercubes | Metric dimension | Minimal doubly resolving setsen
dc.titleComputing minimal doubly resolving sets of graphsen
dc.typeArticleen
dc.identifier.doi10.1016/j.cor.2008.08.002en
dc.identifier.scopus2-s2.0-57749181541en
dc.contributor.affiliationMathematical Institute of the Serbian Academy of Sciences and Arts-
dc.relation.firstpage2149en
dc.relation.lastpage2159en
dc.relation.issue7en
dc.relation.volume36en
dc.description.rankM21a-
item.openairetypeArticle-
item.fulltextNo Fulltext-
item.grantfulltextnone-
item.cerifentitytypePublications-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
crisitem.author.orcid0000-0002-9752-0971-
Show simple item record

SCOPUSTM   
Citations

49
checked on May 6, 2024

Page view(s)

66
checked on May 7, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.