Title of article :
The quadraticminimumspanningtreeproblem:Alowerboundingprocedure
and anefficientsearchalgorithm
Author/Authors :
Temel O¨ ncan ، نويسنده , , AbrahamP.Punnen، نويسنده ,
Issue Information :
ماهنامه با شماره پیاپی سال 2010
Abstract :
In thispaperweconsiderthequadraticminimumspanningtreeproblem(QMSTP)whichisknownto
be NP-hard.Givenacompletegraph,theQMSTPconsistsoffindingaminimumspanningtree(MST)
whereinteractioncostsbetweenpairsofedgesareprescribed.ALagrangianrelaxationprocedureis
devised andanefficientlocalsearchalgorithmwithtabuthresholdingisdeveloped.Computational
experimentsarereportedonstandardtestinstances,randomlygeneratedtestinstancesandquadratic
assignmentproblem(QAP)instancesfromtheQAPLIBbyusingatransformationscheme.Thelocal
search heuristicyieldsverygoodperformanceandtheLagrangianrelaxationproceduregivesthe
tightestlowerboundsforallinstanceswhencomparedtopreviouslowerboundingapproaches.
Keywords :
Quadratic minimum spanning tree problem , Lagrangian relaxation , Local search
Journal title :
Computers and Operations Research
Journal title :
Computers and Operations Research
