Det är ABSTRACT. Det är viktigt att identifiera kritiska noder i en graf för att förstå nätverkets strukturella egenskaper och konnektivitetsegenskaper. I detta dokument fokuserar vi på att upptäcka kritiska noder, eller noder vars radering resulterar i minsta parvisa anslutning mellan de återstående noderna. Detta problem, känt som den CRITIcal NODE PROBLEM har tillämpningar inom flera områden, inklusive biomedicin, telekommunikation och militär strategisk planering. Vi visar att erkännande versionen av problemet är N P - fullständig och härleda en matematisk formulering baserad på heltal linjär programmering. Dessutom föreslår vi en heurism för det problem som utnyttjar grafens kombinatoriska struktur. Den heuristiska förstärks sedan genom tillämpning av en lokal förbättringsmetod. En beräkningsstudie presenteras där vi tillämpar heltal programmering formulering och heuristic till verkliga och slumpmässigt genererade datamängder. För alla testade fall kan heurismen effektivt tillhandahålla optimala lösningar på en bråkdel av den tid som krävs för ett kommersiellt programvarupaket.
Arulselvan m.fl. REF har visat att det kritiska nodproblemet i en graf är ett NP-komplett problem och föreslagit en heuristisk algoritm för det.
Detecting critical nodes in sparse graphs
{'venue': 'Comput. Oper. Res', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}