Title of article
The quadraticminimumspanningtreeproblem:Alowerboundingprocedure and anefficientsearchalgorithm
Author/Authors
Temel O¨ ncan ، نويسنده , , AbrahamP.Punnen، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
12
From page
1762
To page
1773
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
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927782
Link To Document