首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Diameter constrained reliability of ladders and Spanish fans
  • 本地全文:下载
  • 作者:Cancela, Héctor ; Robledo, Franco ; Romero, Pablo
  • 期刊名称:Yugoslav Journal of Operations Research
  • 印刷版ISSN:0354-0243
  • 电子版ISSN:1820-743X
  • 出版年度:2016
  • 页码:4-4
  • DOI:10.2298/YJOR140721004C
  • 出版社:Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Economics Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mechanical Engineering, Belgrade
  • 摘要:We are given a graph G = (V, E), terminal set K  V and diameter d > 0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short), is the probability that the K-diameter is not greater than d in the subgraph induced by non-failed links. The contributions of this paper are two-fold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminals k = jKj and diameter d. Here, we prove that when d > 2 the problem is NP-Hard when K = V. Second, we compute the DCR efficiently for Ladders and Spanish Fans. Open problems and trends for future work are discussed in the conclusions.
  • 关键词:diameter constrained reliability; computational complexity; graph theory
国家哲学社会科学文献中心版权所有