Detecting critical nodes in sparse graphs
作者： Ashwin Arulselvan , Clayton W. Commander , Lily Elefteriadou , Panos M. Pardalos
DOI: 10.1016/J.COR.2008.08.016
关键词: Combinatorial optimization 、 Connectivity 、 Critical graph 、 Linear programming 、 Dense graph 、 Integer programming 、 Commercial software 、 Mathematics 、 Mathematical optimization 、 Heuristics
摘要: Identifying critical nodes in a graph is important to understand the structural characteristics and connectivity properties of network. In this paper, we focus on detecting nodes, or whose deletion results minimum pair-wise among remaining nodes. This problem, known as node problem has applications several fields including biomedicine, telecommunications, military strategic planning. We show that recognition version NP-complete derive mathematical formulation based integer linear programming. addition, propose heuristic for which exploits combinatorial structure graph. The then enhanced by application local improvement method. A computational study presented apply programming real randomly generated data sets. For all instances tested, able efficiently provide optimal solutions fraction time required commercial software package.
core.ac.uk
strath.ac.uk
acm.org
elsevier.com
ufl.edu 
optimization-online.org 
sci-hub.se 参考文章(33)
Gerald J. Lieberman, Frederick S. Hillier, Introduction to Operations Research and Revised CD-ROM 8 Introduction to Operations Research and Revised CD-ROM 8. ,(2005)
Sergiy Butenko, Panagote M. Pardalos, Maximum independent set and related problems, with applications University of Florida. ,(2003)
Carlos A. S. Oliveira, Panos M. Pardalos, Tania M. Querido, INTEGER FORMULATIONS FOR THE MESSAGE SCHEDULING PROBLEM ON CONTROLLER AREA NETWORKS WORLD SCIENTIFIC. pp. 353- 365 ,(2004) , 10.1142/9789812796592_0016
Reiner Horst, Introduction to Global Optimization (Nonconvex Optimization and Its Applications) Springer-Verlag New York, Inc.. ,(2002)
Don Grundel, Robert Murphey, Panos M Pardalos, Theory and algorithms for cooperative systems World Scientific. ,(2004) , 10.1142/5635
Myer Kutz, Handbook of Transportation Engineering ,(2003)
Handbook of optimization in telecommunications Springer. ,(2006) , 10.1007/978-0-387-30165-5
Zhou Tao, Fu Zhongqian, Wang Binghong, Epidemic dynamics on complex networks Progress in Natural Science. ,vol. 16, pp. 452- 457 ,(2006) , 10.1080/10020070612330019
S.P. Borgatti, Identifying sets of key players in a network international conference on integration of knowledge intensive multi agent systems. pp. 127- 131 ,(2003) , 10.1109/KIMAS.2003.1245034
Valdis Krebs, Uncloaking Terrorist Networks First Monday. ,vol. 7, ,(2002) , 10.5210/FM.V7I4.941