ON THE MINIMUM-CARDINALITY-BOUNDED-DIAMETER AND THE BOUNDED-CARDINALITY-MINIMUM-DIAMETER EDGE ADDITION PROBLEMS

作     者：LI, CL MCCORMICK, ST SIMCHILEVI, D 

作者机构：UNIV BRITISH COLUMBIAFAC COMMERCE & BUSINESS ADMVANCOUVER V6T 1W5BCCANADA COLUMBIA UNIVDEPT IND ENGN & OPERAT RESNEW YORKNY 10027 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：1992年第11卷第5期

页      面：303-308页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：National Science Foundation, NSF, (DDM-8922712) National Science Foundation, NSF Office of Naval Research, ONR, (N00014-90-J-1649) Office of Naval Research, ONR Iran Telecommunication Research Center, ITRC, (CDR 84-21402) Iran Telecommunication Research Center, ITRC 

主　　题：COMPUTATIONAL COMPLEXITY NETWORKS GRAPHS TELECOMMUNICATIONS WORST-CASE ANALYSIS 

摘      要：Given a graph G = (V, E), positive integers D Absolute value of V and B, the Minimum-Cardinality-Bounded-Diameter (MCBD) Edge Addition Problem is to find a superset of edges E superset-or-equal-to E such that the graph G = (V, E ) has diameter no greater than D and the total number of the new edges is minimized, while the Bounded-Cardinality-Minimum-Diameter (BCMD) Edge Addition Problem is to find a superset of edges E superset-or-equal-to E with \E \E\ less-than-or-equal-to B such that the diameter of G = (V, E ) is minimized. We prove that the MCBD case is NP-hard even when D = 2 and describe a polynomial heuristic for BCMD with a constant worst-case bound. We also show that finding a polynomial heuristic for MCBD with a constant worst-case bound is no easier than finding such a heuristic for the dominating set problem.