Abstract-Society är starkt beroende av sina nätverkade fysiska infrastruktur och informationssystem. En noggrann bedömning av dessa systems sårbarhet mot störande händelser är av avgörande betydelse för planering och riskhantering. Befintliga metoder för sårbarhetsbedömningar av storskaliga system fokuserar främst på att undersöka inhomogena egenskaper hos de underliggande grafelementen. Dessa åtgärder och tillhörande heuristiska lösningar är begränsade när det gäller att utvärdera sårbarheten hos storskaliga nättopologier. Dessutom misslyckas dessa metoder ofta med att ge resultatgarantier för de föreslagna lösningarna. I detta dokument föreslår vi en sårbarhetsmått, parvis konnektivitet, och använder den för att formulera nätsårbarhetsbedömning som ett graf-teoretiskt optimeringsproblem, som kallas -disruptor. Målet är att identifiera den minsta uppsättning kritiska nätelement, nämligen noder och kanter, vars avlägsnande leder till en specifik försämring av nätets globala parvisa anslutning. Vi bevisar NP-fullständighet och otillnärmning av detta problem och föreslår en (logglogglogg ) pseudo-tillnärmning algoritm för att beräkna uppsättningen kritiska noder och en (log 1 5 ) pseudo-tillnärmning algoritm för att beräkna uppsättningen kritiska kanter. Resultaten av ett omfattande simuleringsbaserat experiment visar genomförbarheten av vårt föreslagna ramverk för sårbarhetsbedömning och effektiviteten hos de föreslagna approximationsalgoritmerna i jämförelse med andra tillvägagångssätt.
En O(log n log log n) pseudo-tillnärmning algoritm föreslogs i REF.
On New Approaches of Assessing Network Vulnerability: Hardness and Approximation
{'venue': 'IEEE/ACM Transactions on Networking', 'journal': 'IEEE/ACM Transactions on Networking', 'mag_field_of_study': ['Computer Science']}