计算机科学 ›› 2014, Vol. 41 ›› Issue (8): 81-84.doi: 10.11896/j.issn.1002-137X.2014.08.017
• 2013年全国理论计算机科学学术年会 • 上一篇 下一篇
潘竹生,莫毓昌,赵建民
PAN Zhu-sheng,MO Yu-chang and ZHAO Jian-min
摘要： 网络可靠度BDD分析的计算复杂度与BDD尺度线性相关,而BDD尺度依赖边排序策略,边排序问题是BDD网络可靠度分析的重要问题。从网络结构特性出发,设计了优先级边排序策略并深入研究了在该策略下不同排序起点对BDD尺度的影响。实验结果表明:源点和网络中心不是高性能排序起点,最佳排序起点分布在网络边缘,网络中心点为最差排序起点。该结论可为揭示边排序影响BDD尺度的本质以及研究高效启发性边排序策略提供重要参考依据。
| [1] Akers B．Binary decision diagrams[J]．IEEE Trans．Computers,1978,C-27:509-516 [2] Bryant R E．Symbolic Boolean manipulation with ordered binary-decision diagrams[J]．ACMComputing Surveys,1992,24(3):293-318 [3] Bryant R E．Graph-Based Algorithms for Boolean Function Manipulation[J]．IEEE trans．on computers,1986,c-35:677-691 [4] Sieling D,Wegener I．Reduction of OBDDs in Linear Time[J]．Information Processing Letters,1993,48(3):139-144 [5] Bollig B,Wegener I．Improving the variable ordering of OBDDs is NP-complete[J]．IEEE trans．on Computers,1996,45(9):993-1002 [6] Friedman S J,Supowit K J．Finding the optimal variable ordering for Binary Decision Diagrams[J]．IEEE trans．on Computer,1990,C-39(5):710-713 [7] Hardy G,Lucet C,Limnios N．Computing all-terminal reliability of stochastic networks with binary decision diagrams[C]∥11th International Symposium on Applied Stochastic Models and Data Analysis．2005:1468-1474 [8] Hardy G,Lucet C,Limnios N．K-Terminal Network Reliability Measures With Binary Decision Diagrams[J]．IEEE Trans．Reliability,2007,6(3):506-515 [9] Yeh F-M,Kuo S-Y．OBDD-based network reliability calculation[J]．Electronics Letters,1997,33(9):759-760 [10] Kuo S Y,Lu S K,Yeh F M．Determining terminal-pair network reliability based on edge expansion diagrams using OBDD[J]．IEEE Trans．Reliability,1999,8(3):234-246 [11] Yeh F-M,Lu S-K,Kuo S-Y．OBDD-based evaluation of k-termi-nal network reliability[J]．IEEE Trans．Reliability,2002,1(4):443-451 [12] Butler K M,Ross D E,Kapur R,et al．Heuristics to Compute Variable Orderings for Efficient Manipulation of Ordered Binary Decision Diagrams[C]∥Proc．28th ACM/IEEE Design Automation Conf.．1991:417-420 [13] Fujita M,Fujisawa H,Kawato N．Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams[C]∥Proc．IEEE Int’l Conf．Computer Aided Design．1988:2-5 [14] Fujita M,Matsunaga Y,Kakuda T．On variable Ordering of Binary Decision Diagrams for the Application of Multi-Level Logic Synthesis[C]∥Proc．European Design Automation Conf.．1991:50-54 [15] Mercer M R,Kapur R,Ross D E．Functional Approaches toGenerating Orderings for Efficient Symbolic Representation[C]∥Proc．29th ACMIIEEE Design Automation Conf．．1992:614-619 [16] Bouissou M．An ordering heuristic for building binary decisiondiagrams from fault-trees[C]∥Proc．Annu．Reliab．Maintainability Symp.．1996:208-214 [17] Herrmann J U,Soh S．A Space Efficient Algorithm for Network Reliability[C]∥IEEE,the 15th Asia-Pacific Conf．Communications (APCC2009)．2009:703-707 [18] Herrmann J U．Improving Reliability Calculation with Augmented Binary Decision Diagrams[C]∥IEEE,Advanced Information Networking and Applications (AINA2012)．2012:329-333 [19] Herrmann J U,Soh S．Comparison of binary and multi-variate hybrid decision diagram algorithms for k-terminal reliability[C]∥Proceedings of the Thirty-Fourth Australasian Computer Science Conference-Volume113．Australian Computer Society,Inc.,2011:153-162 [20] Pan Z S,Mo Y C,Zhong F R,et al．Performance Improvement of BDD-based Network Reliability[J]．Computer engineering &science,2012,4(9):50-56 |
| No related articles found! |
|
||
首页