Title of article
Detecting criticalnodesinsparsegraphs
Author/Authors
Ashwin Arulselvan، نويسنده , , ClaytonW.Commanderb، نويسنده , , LilyElefteriadouc، نويسنده , , PanosM.Pardalosa، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2009
Pages
8
From page
2193
To page
2200
Abstract
Identifying criticalnodesinagraphisimportanttounderstandthestructuralcharacteristicsandthe
connectivity propertiesofthenetwork.Inthispaper,wefocusondetectingcriticalnodes,ornodes
whose deletionresultsintheminimumpair-wiseconnectivityamongtheremainingnodes.Thisproblem,
known asthe critical nodeproblem has applicationsinseveralfieldsincludingbiomedicine,telecom-
munications, andmilitarystrategicplanning.Weshowthattherecognitionversionoftheproblemis
NP-complete andderiveamathematicalformulationbasedonintegerlinearprogramming.Inaddition,
we proposeaheuristicfortheproblemwhichexploitsthecombinatorialstructureofthegraph.The
heuristic isthenenhancedbytheapplicationofalocalimprovementmethod.Acomputationalstudyis
presented inwhichweapplytheintegerprogrammingformulationandtheheuristictorealandrandomly
generated datasets.Forallinstancestested,theheuristicisabletoefficientlyprovideoptimalsolutions
in afractionofthetimerequiredbyacommercialsoftwarepackage.
Keywords
Critical node detection , Heuristics , Combinatorial optimization , NP-complete , Integer linear programming
Journal title
Computers and Operations Research
Serial Year
2009
Journal title
Computers and Operations Research
Record number
927604
Link To Document