Speeding up Computation of the Reliability Polynomial Coefficients for a Random Graph

被引：3
|
作者：
Rodionov, A. S. [1 ]
机构：
[1] Russian Acad Sci, Inst Computat Math & Math Geophys, Siberian Branch, Novosibirsk, Russia
来源：
AUTOMATION AND REMOTE CONTROL | 2011年 / 72卷 / 07期
关键词：
Remote Control; Span Tree; Random Graph; Exact Computation; Network Reliability;
D O I：
10.1134/S0005117911070150
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We consider the problem of computing the coefficients of the reliability polynomial (RP) for a random graph with reliable vertices and unreliable edges. To speed up the computation, we use the meaning of RP coefficients in one of its representations and prove vector relations over vectors of binomial coefficients.
引用
收藏
页码：1474 / 1486
页数：13
相关论文
共 50 条
  • [41] Computation of the asymptotics of solutions for equations with polynomial degeneration of the coefficients
    D. S. Kats
    Differential Equations, 2015, 51 : 1589 - 1594
  • [42] Speeding Up SSFEM Computation Using Kronecker Tensor Products
    Gaignaire, R.
    Guyomarc'h, F.
    Moreau, O.
    Clenet, S.
    Sudret, B.
    IEEE TRANSACTIONS ON MAGNETICS, 2009, 45 (03) : 1432 - 1435
  • [43] Coefficients of the Characteristic Polynomial of the (Signless, Normalized) Laplacian of a Graph
    Guo, Ji-Ming
    Li, Jianxi
    Huang, Peng
    Shiu, Wai Chee
    GRAPHS AND COMBINATORICS, 2017, 33 (05) : 1155 - 1164
  • [44] Coefficients of the Characteristic Polynomial of the (Signless, Normalized) Laplacian of a Graph
    Ji-Ming Guo
    Jianxi Li
    Peng Huang
    Wai Chee Shiu
    Graphs and Combinatorics, 2017, 33 : 1155 - 1164
  • [45] Coefficients of the Tutte polynomial and minimal edge cuts of a graph
    Chen, Haiyan
    Guo, Mingxu
    ADVANCES IN APPLIED MATHEMATICS, 2025, 166
  • [46] CLIQUE PARTITIONS, GRAPH COMPRESSION AND SPEEDING-UP ALGORITHMS
    FEDER, T
    MOTWANI, R
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 51 (02) : 261 - 272
  • [47] Sparsification-a technique for speeding up dynamic graph algorithms
    Univ of California, Irvine, Irvine, United States
    J ACM, 5 (669-696):
  • [48] Speeding-up Construction Algorithms for the Graph Coloring Problem
    Kanahara, Kazuho
    Katayama, Kengo
    Miyake, Takafumi
    Tomita, Etsuji
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105 (08)
  • [49] An Approach to Improving Reliability of Parallel Graph Computation
    Cui, Jin
    Duan, Zhenhua
    THEORETICAL ASPECTS OF SOFTWARE ENGINEERING, TASE 2024, 2024, 14777 : 58 - 72
  • [50] Speeding up problem solving by abstraction: A graph oriented approach
    Holte, RC
    Mkadmi, T
    Zimmer, RM
    MacDonald, AJ
    ARTIFICIAL INTELLIGENCE, 1996, 85 (1-2) : 321 - 361
12345