Computing Critical Nodes in Directed Graphs

DOI10.1145/3228332zbMath1430.68234OpenAlexW2884830210WikidataQ129560144 ScholiaQ129560144MaRDI QIDQ4555541

Nilakantha Paudel, Giuseppe F. Italiano, Loukas Georgiadis

Publication date: 20 November 2018

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3228332

zbMATH Keywords

combinatorial optimizationdirected graphsNP-hardnessstrong connectivitystrong articulation pointscritical nodes

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ EIA-CNDP: an exact iterative algorithm for critical node detection problem

Cites Work

• Unnamed Item
• Finding strong bridges and strong articulation points in linear time
• Detecting critical nodes in sparse graphs
• Edge-disjoint spanning trees and depth-first search
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• A faster algorithm for betweenness centrality*
• Emergence of Scaling in Random Networks
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
• Finding Dominators in Directed Graphs
• Dominators in Linear Time
• Strong Connectivity in Directed Graphs under Failures, with Applications
• 2-Edge Connectivity in Directed Graphs
• Computing Critical Nodes in Directed Graphs
• Finding Dominators in Practice
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Computing Critical Nodes in Directed Graphs