skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices

A Fast Greedy Algorithm for the Critical Node Detection Problem

Ventresca, Mario ; Aleman, Dionne

Combinatorial Optimization and Applications, p.603-612 [Periódico revisado por pares]

Cham: Springer International Publishing

Texto completo disponível

Citações Citado por
  • Título:
    A Fast Greedy Algorithm for the Critical Node Detection Problem
  • Autor: Ventresca, Mario ; Aleman, Dionne
  • Assuntos: Critical Vertex ; Population-based Incremental Learning Algorithms ; Residual Graph ; Small Network Instances ; Varying Edge Weights
  • É parte de: Combinatorial Optimization and Applications, p.603-612
  • Descrição: The critical node detection problem (CNDP) aims to fragment a graph \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} =(V,E) end{document} by removing a set of vertices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} end{document} with cardinality \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} R|\le K end{document} such that the residual graph has minimum pairwise connectivity. Algorithms that are capable of finding \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} end{document} in graphs with many thousands or millions of vertices are needed since existing approaches require significant computational cost and subsequently are useful for only very small network instances. An efficient method for evaluating the impact of removing any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} \in V end{document} on the CNDP objective function within reasonable time and space complexity is then necessary. In this paper we propose a depth-first search solution to this problem that requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} mathcal {O}(|V|+|E|) end{document} complexity, and employ the method in a greedy algorithm for quickly identifying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} end{document} in large networks. We evaluate the results using six real-world benchmark problems. The proposed algorithm can be easily extended to vertex and edge-weighted variants of the critical vertex detection problem.
  • Editor: Cham: Springer International Publishing
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.