Complexity of Reducing the Delay between Two Nodes by Node-based and Edge-based Upgrading Strategies

Complexity of Reducing the Delay between Two Nodes by Node-based and Edge-based Upgrading Strategies

导出

摘要 For a pair of nodes s, t in an undirected graph G = (V, A) and a given level U of allowable delay, we would like to modify the network by node-based or edge-based upgrading strategies to make the delay between s and t not greater than U. In this paper, we present some NP-hard results for the delay improvement problems.

作者 Xiao-guangYang Jian-zhongZhang

机构地区 LaboratoryofManagement DepartmentofMathematics

出处《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2004年第4期589-596,共8页 应用数学学报（英文版）

关键词 Node-based upgrade edge-based upgrade even-odd partition hard Node-based upgrade edge-based upgrade even-odd partition hard

分类号 O157.5 [理学—基础数学]

引文网络
相关文献

参考文献8

1Dranmeister, K.U. et al. Modifying edges of a network to obtain short subgraphs. Theoretical Computer Science, 203:91-121 (1998)
2Garey, M.R., Johnson, D.S. Computers and Intractability: A Guide of the Theory of NP-Completeness,Freeman, San Francisco, 1979
3Hambrush, S.E. Tu, H.Y. Edge weight reduction problems in directed acyclic graphs. Journal of Algorithms,24:66-93 (1997)
4Krumke, S.O. et al. Approximation algorithms for certain network improvement problems. Journal of Combinatorial Optimization, 2:257-288 (1998)
5Krumke, S.O. et al. Improving spanning trees by upgrading nodes. Theoretical Computer Science, 221:139-155 (1999)
6Krumke, S.O. et al. Improving minimum cost spanning trees by upgrading nodes. Journal of Algorithms,33:92-111 (1999)
7Krumke, S.0. et al. Upgrading bottleneck constrained forests. Discrete Applied Mathematics 108:129-142(2001)
8Paik, D., Sahni, S. Network upgrading problems. Networks, 26:45-58 (1995)

1HE Lin-feng,ZHANG Bai-sheng,LI Tian-fu,TIAN Geng-fang,ZU Yong,HAN Wen-ze,LIU Rong-deng.Upgrading of the Neutron Powder Diffractometer[J].Annual Report of China Institute of Atomic Energy,2006(1):116-117.
2Franco Brezzi,黄际政,孙宇阳.VEM的伟大的美[J].数学译林,2014,0(4):291-291.
3WANG Zhi-qiang, LIU Yi-na, LI Chun-juan, LUO Hai-long.Testing for Project of National Key Laboratory of Metrology and Calibration Technology[J].Annual Report of China Institute of Atomic Energy,2008(1):171-171.
4M.Imran Jamil,Bilal Masud,Faisal Akram,S.M.Sohail Gilani.D^0D^^0＊(D^0D^0＊) system in QCD-improved many body potential[J].Chinese Physics C,2017,41(1):60-71.
5John P. Collins,Joep J. H. M. Font Freide,Barry Nay.A History of Fischer-Tropsch Wax Upgrading at BP-from Catalyst Screening Studies to Full Scale Demonstration in Alaska[J].Journal of Natural Gas Chemistry,2006,15(1):1-10. 被引量：5
6CAO HuaiXin LI Li CHEN ZhengLi ZHANG Ye GUO ZhiHua.Restricted allowable generalized quantum gates[J].Chinese Science Bulletin,2010,55(20):2122-2125. 被引量：14
7Wei Xiaomei,Zhou Min,Zhang Chun,Lei Jiali,Song Liqiang.Upgrading of Yi'an gas coal by low temperature pyrolysis under different atmospheres[J].Mining Science and Technology,2011,21(3):401-405. 被引量：4
8Pasu Kaewplung,Wadis Kasantikul.Simple and Practical Approaches for Upgrading Installed Electronic-Repeater-Based Fiber Systems to Optically Amplified Systems[J].光学学报,2003,23(S1):531-532.
9方新贵,王敏.A PACKING PAIR OF GRAPHS {(P,P-1), (P,P)} AND SLATER'S PROBLEMS[J].Chinese Science Bulletin,1988,33(16):1402-1403.
10芮洪兴.DOMAIN DECOMPOSITION ALGORITHM FOR TWO PHASE DISPLACEMENT PROBLEM IN POROUS MEDIA[J].Acta Mathematica Scientia,1998,18(S1):5-15.

Acta Mathematicae Applicatae Sinica

2004年第4期

浏览历史

内容加载中请稍等...

Complexity of Reducing the Delay between Two Nodes by Node-based and Edge-based Upgrading Strategies

参考文献8

相关作者

相关机构

相关主题

浏览历史