检索结果-内蒙古大学图书馆

A general Evolutionary Framework for different classes of Critical Node Problems

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2016年 55卷 128-145页

作者： Aringhieri, Roberto Grosso, Andrea Hosteins, Pierre Scatamacchia, Rosario Univ Turin Dipartimento Informat Corso Svizzera 185 I-10149 Turin Italy Politecn Torino Dipartimento Automat & Informat Corso Duca degli Abruzzi 24 I-10129 Turin Italy

We design a flexible Evolutionary Framework for solving several classes of the Critical Node Problem (CNP), i.e. the maximal fragmentation of a graph through node deletion, given a measure of connectivity. The algorithm uses greedy rules in order to lead the search towards good quality solutions during reproduction and mutation phases. Such rules, which are only partially reported in the literature, are generalised and adapted to the six different formulations of the CNP considered along the paper. The link between solutions of different CNP formulations is investigated, both quantitatively and qualitatively. Furthermore, we provide a comparison with best known results when those are available in literature that confirms the good overall quality of our solutions. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Evolutionary algorithm Critical Node Problem graph fragmentation Greedy rules Connectivity measures

来源：评论

学校读者我要写书评

暂无评论

Network dismantling

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2016年第44期113卷 12368-12373页

作者： Braunstein, Alfredo Dall'Asta, Luca Semerjian, Guilhem Zdeborova, Lenka Politecn Torino Dept Appl Sci & Technol Corso Duca Abruzzi 24 I-10129 Turin Italy Human Genet Fdn Via Nizza 52 I-10126 Turin Italy Coll Carlo Alberto Via Real Coll 30 I-10024 Moncalieri Italy Univ Paris 06 Sorbonne Univ Paris Sci & Lettres PSL Res Univ Lab Phys TheorEcole Normale SuperCNRS F-75005 Paris France CEA CNRS Inst Phys Theor F-91191 Gif Sur Yvette France Univ Paris Saclay F-91191 Gif Sur Yvette France

We study the network dismantling problem, which consists of determining a minimal set of vertices in which removal leaves the network broken into connected components of subextensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices, leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading, we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective, we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide additional insights into the dismantling problem, concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well-performing nodes.

关键词： graph fragmentation message passing percolation random graphs influence maximization

来源：评论

学校读者我要写书评

暂无评论

Hybrid constructive heuristics for the critical node problem

引用

ANNALS OF OPERATIONS RESEARCH 2016年第1-2期238卷 637-649页

作者： Addis, Bernardetta Aringhieri, Roberto Grosso, Andrea Hosteins, Pierre Univ Lorraine INRIA Nancy Grand Est CNRS UMR 7503 LORIA Vandoeuvre Les Nancy France Univ Turin Dipartimento Informat I-10149 Turin Italy

We consider the Critical Node Problem: given an undirected graph and an integer number K, at most K nodes have to be deleted from the graph in order to minimize a connectivity measure in the residual graph. We combine the basic steps used in common greedy algorithms with some flavour of local search, in order to obtain simple hybrid heuristic algorithms. The obtained algorithms are shown to be effective, delivering improved performances (solution quality and speed) with respect to known greedy algorithms and other more sophisticated state of the art methods.

关键词： Critical node problem graph fragmentation Hybrid heuristics

来源：评论

学校读者我要写书评

暂无评论

A Genetic Algorithm for a class of Critical Node Problems

引用

Electronic Notes in Discrete Mathematics 2016年 52卷 359-366页

作者： Aringhieri, Roberto Grosso, Andrea Hosteins, Pierre Dipartimento di Informatica Università degli Studi di Torino Turin Italy

In this paper, we deal with two different variants of the Critical Node Problem, designing a flexible genetic algorithm for tackling them both. The results are compared with the best known results available in the lit... 详细信息

关键词： Cardinality-Constrained Critical Node Problem Genetic algorithm graph fragmentation

来源：评论

学校读者我要写书评

暂无评论

VNS solutions for the critical node problem

引用

Electronic Notes in Discrete Mathematics 2015年 47卷 37-44页

作者： Aringhieri, Roberto Grosso, Andrea Hosteins, Pierre Scatamacchia, Rosario Dipartimento di Informatica Università degli Studi di Torino Turin Italy Dipartimento di Automatica e Informatica Politecnico di Torino Turin Italy

We present a VNS algorithm for the Critical Node Problem, i.e., the maximal fragmentation of a graph through the deletion of k nodes. Two computational efficient neighbourhoods are proposed proving also their equivalence to the straightforward exchange of two nodes. The results of the proposed VNS algorithms outperform those currently available in literature. © 2014 Elsevier B.V.

关键词： Critical node problem graph fragmentation

来源：评论

学校读者我要写书评

暂无评论

A preliminary analysis of the Distance Based Critical Node Problem

引用

Electronic Notes in Discrete Mathematics 2016年 55卷 25-28页

We discuss how to develop efficient heuristics for the distance based critical node problem, that is the problem of deleting a subset of nodes from a graph G in such a way that the distance between each pair of nodes ... 详细信息

关键词： Critical Node Problem graph fragmentation Shortest Paths

来源：评论

学校读者我要写书评

暂无评论

Local search metaheuristics for the critical node problem

引用

NETWORKS 2016年第3期67卷 209-221页

作者： Aringhieri, Roberto Grosso, Andrea Hosteins, Pierre Scatamacchia, Rosario Univ Turin Dipartimento Informat I-10149 Turin Italy Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy

We present two metaheuristics for the Critical Node Problem, that is, the maximal fragmentation of a graph through the deletion of k nodes. The two metaheuristics are based on the Iterated Local Search and Variable Neighborhood Search frameworks. Their main characteristic is to exploit two smart and computationally efficient neighborhoods which we show can be implemented far more efficiently than the classical neighborhood based on the exchange of any two nodes in the graph, and which we prove is equivalent to the classical neighborhood in the sense that it yields the same set of neighbors. Solutions to improve the overall running time without deteriorating the quality of the solution computed are also illustrated. The results of the proposed metaheuristics outperform those currently available in literature. (c) 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 209-221 2016

关键词： critical node problem graph fragmentation metaheuristics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：