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

Heuristic Search with Cut Point Based Strategy for critical node problem

Journal of Computer Science & Technology 2024年第6期39卷 1328-1340页

作者： Zhi-Han Chen Shao-Wei Cai Jian Gao Shi-Ke Ge Chan-Juan Liu Jin-Kun Lin School of Computer Science and Technology University of Chinese Academy of SciencesBeijing 101408China Key Laboratory of System Software(Chinese Academy of Sciences)and State Key Laboratory of Computer Science Institute of SoftwareChinese Academy of SciencesBeijing 100190China College of Information Science and Technology Northeast Normal UniversityChangchun 130024China School of Computer Science and Technology Dalian University of TechnologyDalian 116024China SeedMath Technology Limited Beijing 100086China

The critical node problem(CNP)aims to deal with critical node identification in a graph,which has extensive applications in many *** CNP is a challenging task due to its computational complexity,and it attracts much attention from both academia and *** this paper,we propose a population-based heuristic search algorithm called CPHS(Cut Point Based Heuristic Search)to solve CNP,which integrates two main *** first one is a cut point based greedy strategy in the local search,and the second one involves the functions used to update the solution pool of the ***,a mutation strategy is applied to solutions with probability based on the overall average similarity to maintain the diversity of the solution *** are performed on a synthetic benchmark,a real-world benchmark,and a large-scale network benchmark to evaluate our *** with state-of-the-art algorithms,our algorithm has better performance in terms of both solution quality and run time on all the three benchmarks.

关键词： local search cut point heuristic search critical node problem

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Multilevel Approaches for the critical node problem

引用

OPERATIONS RESEARCH 2021年第2期69卷 486-508页

作者： Baggio, Andrea Carvalho, Margarida Lodi, Andrea Tramontani, Andrea SwissQuant Grp AG Quant Res CH-8001 Zurich Switzerland Univ Montreal CIRRELT Montreal PQ H3T 1J4 Canada Univ Montreal DIRO Montreal PQ H3T 1J4 Canada Ecole Polytech Montreal Montreal PQ H3T 1J4 Canada IBM Corp CPLEX Optimizat I-40132 Bologna Italy

In recent years, a lot of effort has been dedicated to develop strategies to defend networks against possible cascade failures or malicious viral attacks. On the one hand, network safety is investigated from a preventive perspective. On the other hand, blocking models have been proposed for scenarios in which the attack has already taken place causing a harmful spreading throughout the network. In this work, we combine these two perspectives. More precisely, following the framework defender-attacker-defender, we consider a model of prevention, attack, and damage containment using a three-stage, zero-sum game. The defender is not only able to adopt preventive strategies, but also to defend the network after an attack takes place. Assuming that the attacker acts optimally, we compute a defensive strategy for the first stage that minimizes the total damage to the network in the end of the third stage. Our contribution consists of considering this problem as a trilevel mixed-integer program and designing an exact algorithm for it based on tools developed for multilevel programming.

关键词： multilevel programming critical node problem firefighter problem mixed-integer programming defender-attacker-defender

来源：评论

学校读者我要写书评

暂无评论

Complexity of the critical node problem over trees

引用

COMPUTERS & OPERATIONS RESEARCH 2011年第12期38卷 1766-1774页

作者： Di Summa, Marco Grosso, Andrea Locatelli, Marco Univ Turin Dipartimento Informat I-10149 Turin Italy Univ Parma Dipartimento Ingn Informat I-43124 Parma Italy Ecole Polytech Fed Lausanne EPFL SB MATHAA DISOPT Stn 8 CH-1015 Lausanne Switzerland

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. In particular, we study the case where the physical network represented by graph G has a hierarchical organization, so that G is a tree. The NP-completeness of this problem for general graphs has been already established (Arulselvan et al.). We study the subclass of CNP over trees, generalizing the objective function and constraints to take into account general nonnegative "costs" of node connections and "weights" for the nodes that are to be removed. We prove that CNP over trees is still NP-complete when general connection costs are specified, while the cases where all connections have unit cost are solvable in polynomial time by dynamic programming approaches. For the case with nonnegative connection costs and unit node weights we propose an enumeration scheme whose time complexity is within a polynomial factor from 0(1.618034"), where n is the number of nodes of the tree. Results from computational experiments are reported for all the proposed algorithms. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Complexity critical node problem Multicut in trees Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

The Connected critical node problem

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 235-255页

作者： Hosteins, Pierre Scatamacchia, Rosario Grosso, Andrea Aringhieri, Roberto Univ Gustave Eiffel ESTAS COSYS F-59650 Lille France Politecn Torino Dipartimento Ingn Gest & Prod Corso Duca Abruzzi 24 I-10129 Turin Italy Univ Torino Dipartimento Informat Corso Svizzera 185 I-10149 Turin Italy

The critical node problem is a well-known optimisation problem that aims to find the subset of nodes in a graph whose removal impacts the graph connectivity as much as possible according to a specific connectivity measure. In this work, we study a new version of the critical node problem, which we call the Connected critical node problem, where the set of the removed nodes has to form a connected subgraph. We consider three connectivity measures and provide complexity results and solution approaches for general graphs and specific classes of graphs such as graphs with bounded treewidth, trees and series-parallel graphs. We consider the Connected critical node problem where the pairwise connectivity (related to the number of pairs of vertices still connected in the graph) is minimised. We prove that this problem is strongly NP-hard and inapproximable on general graphs and is polynomial-time solvable on graphs with bounded treewidth and with unit connection costs. Further, we prove the NP-hardness of the problem with arbitrary connection costs over trees and series-parallel graphs and derive dynamic programming algorithms. We extend our results to the problem variants that consider the minimisation of the largest connected component and the maximisation of the number of connected components (also called K-way Vertex Cut problem). As side results, we provide new complexity results for the classic critical node problem on series-parallel graphs. (c) 2022 Elsevier B.V. All rights reserved.

关键词： critical node problem Complexity Dynamic programming Treewidth Trees Series-parallel graphs K-way Vertex Cut problem

来源：评论

学校读者我要写书评

暂无评论

An optimal approach for the critical node problem using semidefinite programming

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2017年 471卷 315-324页

作者： Jiang, Cheng Liu, Zhonghua Wang, Juyun Yu, Hua Guo, Xiaoling Univ Chinese Acad Sci Sch Engn Sci Beijing 100049 Peoples R China Commun Univ China Sch Sci Beijing 100024 Peoples R China China Univ Min & Technol Dept Math Beijing 100083 Peoples R China

Detecting critical nodes in complex networks (CNP) has great theoretical and practical significance in many disciplines. The existing formulations for CNP are mostly, as we know, based on the integer linear programming model. However, we observed that, these formulations only considered the sizes but neglected the cohesiveness properties of the connected components in the induced network. To solve the problem and improve the performance of CNP solutions, we construct a novel nonconvex quadratically constrained quadratic programming (QCQP) model and derive its approximation solutions via semidefinite programming (SDP) technique and heuristic algorithms. Various types of synthesized and real-world networks, in the context of different connectivity patterns, are used to validate and verify the effectiveness of the proposed model and algorithm. Experimental results show that our method improved the state of the art of the CNP. (C) 2016 Elsevier B.V. All rights reserved.

关键词： critical node problem Quadratically constrained quadratic programming Semidefinite programming Network optimization

来源：评论

学校读者我要写书评

暂无评论

A fast tri-individual memetic search approach for the distance-based critical node problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第2期308卷 540-554页

作者： Zhou, Yangming Wang, Gezi Hao, Jin-Kao Geng, Na Jiang, Zhibin Shanghai Jiao Tong Univ Data Driven Management Decis Making Lab Shanghai 200030 Peoples R China Shanghai Jiao Tong Univ Sino US Global Logist Inst Antai Coll Econ & Management Shanghai 200030 Peoples R China East China Univ Sci & Technol Dept Comp Sci & Engn Shanghai 200237 Peoples R China Univ Angers Dept Comp Sci F-49045 Angers France

The distance-based critical node problem involves identifying a subset of nodes in a graph such that the removal of these nodes leads to a residual graph with the minimum distance-based connectivity. Due to its NP-hard nature, solving this problem using exact algorithms has proved to be highly challenging. Moreover, existing heuristic algorithms are typically time-consuming. In this work, we introduce a fast tri-individual memetic search approach to solve the problem. The proposed approach maintains a small population of only three individuals during the whole search. At each generation, it sequentially executes an inherit-repair recombination operator to generate a promising offspring solution, a fast betweenness centrality-based late-acceptance search to find high-quality local optima, and a simple population updat-ing strategy to maintain a healthy population. Extensive experiments on both real-world and synthetic benchmarks show our method significantly outperforms state-of-the-art algorithms. In particular, it can steadily find the known optimal solutions for all 22 real-world instances with known optima in only one minute, and new upper bounds on the remaining 22 large real-world instances. For 54 synthetic in-stances, it finds new upper bounds on 36 instances, and matches the previous best-known upper bounds on 15 other instances in ten minutes. Finally, we investigate the usefulness of each key algorithmic in-gredient.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization critical node problem Distance -based connectivity Metaheuristic Memetic search

来源：评论

学校读者我要写书评

暂无评论

The stochastic critical node problem over trees

引用

NETWORKS 2020年第3期76卷 381-401页

作者： Hosteins, Pierre Scatamacchia, Rosario Univ Gustave Eiffel COSYS ESTAS F-59666 Lille France Politecn Torino Dipartimento Ingn Gest & Prod Turin Italy

We tackle a stochastic version of the critical node problem (CNP) where the goal is to minimize the pairwise connectivity of a graph by attacking a subset of its nodes. In the stochastic setting considered, the outcome of attacks on nodes is uncertain. In our work, we focus on trees and demonstrate that over trees the stochastic CNP actually generalizes to the stochastic critical element detection problem where the outcome of attacks on edges is also uncertain. We prove the NP-completeness of the decision version of the problem when connection costs are one, while its deterministic counterpart was proved to be polynomial. We then derive a nonlinear model for the considered CNP version over trees and provide a corresponding linearization based on the concept ofprobability chains. Moreover, given the features of the derived linear model, we devise an exact Benders decomposition (BD) approach where we solve the slave subproblems analytically. A strength of our approach is that it does not rely on any statistical approximation such as the sample average approximation, which is commonly employed in stochastic optimization. We also introduce an approximation algorithm for the problem variant with unit connection costs and unit attack costs, and a specific integer linear model for the case where all the survival probabilities of the nodes in case of an attack are equal. Our methods are capable of solving relevant instances of the problem with hundreds of nodes within 1 hour of computational time. With this work, we aim to foster research on stochastic versions of the CNP, a problem tackled mainly in deterministic contexts so far. Interestingly, we also show a successful application of the concept of probability chains for problem linearizations significantly improved by decomposition methods such as the BD.

关键词： approximation algorithm Benders decomposition critical element detection critical node problem network interdiction probability chains stochastic integer programming trees

来源：评论

学校读者我要写书评

暂无评论

Polynomial and pseudo-polynomial time algorithms for different classes of the Distance critical node problem

引用

DISCRETE APPLIED MATHEMATICS 2019年 253卷 103-121页

作者： Aringhieri, Roberto Grosso, Andrea Hosteins, Pierre Scatamacchia, Rosario Univ Torino Dipartimento Informat Corso Svizzera 185 I-10149 Turin Italy INESC TEC Rua Dr Roberto Frias 378 P-4200 Porto Portugal Politecn Torino Dipartimento Ingn Gest & Prod Corso Duca Abruzzi 24 I-10129 Turin Italy

We study the Distance critical node problem, a generalisation of the critical node problem where the distances between node pairs impact on the objective function. We establish complexity results for the problem according to specific distance functions and provide polynomial and pseudo-polynomial algorithms for special graph classes such as paths, trees and series-parallel graphs. We also provide additional insights about special cases of the critical node problem variants already tackled in the literature. (C) 2018 Elsevier B.V. All rights reserved.

关键词： critical node problem Connectivity measure Shortest paths Dynamic programming Polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

The critical node problem Based on Connectivity Index and Properties of Components on Trees

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2021年第1期38卷

作者： Guan, Xiucui Liu, Chao Zhang, Qiao Southeast Univ Sch Math Nanjing 210096 Peoples R China

We deal with the critical node problem (CNP) in a graph G, in which a given number K of nodes are removed to minimize the connectivity of the residual graph in some sense. Several ways to minimize some connectivity measurement have been proposed, including minimizing the connectivity index(MinCI), maximizing the number of components, minimizing the maximal component size. We propose two classes of CNPs by combining the above measurements together. The objective is to minimize the sum of connectivity indexes and the total degrees in the residual graph. The CNP with an upper-bound M on the maximal component size is denoted by MSCID-CS and the one with an extra upper-bound P on the number of components is denoted by MSCID-CSN. They are generalizations of the MinCI, which has been shown NP-hard for general graphs. In particular, we study the case where G is a tree. Two dynamic programming algorithms are proposed to solve the two classes of CNPs. The time complexities of the algorithms for MSCID-CS and MSCID-CSN are O(n2K2M2) and O(n2K2M2P2), respectively, where n is the number of nodes in G. Computational experiments are presented which show the effectiveness of the algorithms.

关键词： critical node problem tree dynamic programming connectivity index

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：