Computing Critical Nodes in Directed Graphs

DOI10.1145/3228332MaRDI QIDQ4555541zbMATH OpenOpenAlexWikidataFDO

Authors Nilakantha Paudel, Loukas Georgiadis, Giuseppe F. Italiano

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 optimizationcritical nodesdirected graphsNP-hardnessstrong articulation pointsstrong connectivity

Mathematics Subject Classification ID

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

Recommendations

• Computing critical nodes in directed graphs
• Branch and cut algorithms for detecting critical nodes in undirected graphs
• Detecting critical node structures on graphs: a mathematical programming approach
• scientific article; zbMATH DE number 7059791
• Detecting critical nodes in sparse graphs
• Component-cardinality-constrained critical node problem in graphs
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• The connected critical node problem

Cites work

• 2-Edge Connectivity in Directed Graphs
• A faster algorithm for betweenness centrality*
• Computing critical nodes in directed graphs
• Depth-First Search and Linear Graph Algorithms
• Detecting critical nodes in sparse graphs
• Dominators in Linear Time
• Edge-disjoint spanning trees and depth-first search
• Emergence of Scaling in Random Networks
• Finding 2-edge and 2-vertex strongly connected components in quadratic time
• Finding Dominators in Directed Graphs
• Finding Dominators in Practice
• Finding strong bridges and strong articulation points in linear time
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
• Strong connectivity in directed graphs under failures, with applications

Cited in

(5)

• EIA-CNDP: an exact iterative algorithm for critical node detection problem
• A fast greedy algorithm for the critical node detection problem
• scientific article; zbMATH DE number 841597 (Why is no real title available?)
• Strong connectivity in directed graphs under failures, with applications
• Computing critical nodes in directed graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4555541)