Title of article :
Computingminimaldoublyresolvingsetsofgraphs
Author/Authors :
Jozef Kratica، نويسنده , , Mirjana Cangalovi cb، نويسنده , , VeraKova cevi c-Vuj ci cb، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2009
Abstract :
In thispaperweconsidertheminimaldoublyresolvingsetsproblem(MDRSP)ofgraphs.Weprovethat
the problemisNP-hardandgiveitsintegerlinearprogrammingformulation.Theproblemissolvedby
a geneticalgorithm(GA)thatusesbinaryencodingandstandardgeneticoperatorsadaptedtotheprob-
lem. ExperimentalresultsincludethreesetsofORLIBtestinstances:crewscheduling,pseudo-boolean
and graphcoloring.GAisalsotestedontheoreticallychallenginglarge-scaleinstancesofhypercubes
and Hamminggraphs.OptimalityofGAsolutionsonsmallersizeinstanceshasbeenverifiedbytotal
enumeration. Forseverallargerinstancesoptimalityfollowsfromtheexistingtheoreticalresults.TheGA
results forMDRSPofhypercubesareusedbyadynamicprogrammingapproachtoobtainupperbounds
for themetricdimensionoflargehypercubesupto290 nodes, thatcannotbedirectlyhandledbythe
computer.
Keywords :
Evolutionary approach , Minimal doubly resolving sets , Genetic algorithms , Metric dimension , Hypercubes
Journal title :
Computers and Operations Research
Journal title :
Computers and Operations Research
