Short-Time Scaling of Variable Orderingof OBDDs

Abstract

A short-time scaling criterion of variable ordering of OBDDs is proposed. By this criterion it is easy and fast to determine which one is better when several. variable orders are given, especially when they differ 10% or more in resulted BDD size from each other. An adaptive variable order selection method, based on the short-time scaling criterion, is also presented. The experimental results show that this method is efficient and it makes the heuristic variable ordering methods more practical.

Key words: cohesion; object-orientation; class; program complexity; dependence analysis;

Long Wangning; Min Yinghua; Yang Shiyuan; Tong Shibai;. Short-Time Scaling of Variable Orderingof OBDDs[J]., 1997, 12(4): 366-371.

References

[1] Randal E Bryant. Graph-based algorithms for Boolean function Manipulation. IEEE Trans.Computers, 1986, C-35: 677-691.

[2] Fujita M, Fujisawa H, Matsunaga Y. Variable ordering algorithms for ordered binary decision diagram and their evaluation. IEEE Trans. CAD, 1993, 12: 6-12.

[3] Fujii H, Ootomo G, Hori C. Interleaving based variable ordering methods for ordered binary decision diagrams. In IEEE ICCAD'93, pp.38-41. ……….

Related Articles 15

[1]	Yi Zhong, Jian-Hua Feng, Xiao-Xin Cui, Xiao-Le Cui. Machine Learning Aided Key-Guessing Attack Paradigm Against Logic Block Encryption [J]. Journal of Computer Science and Technology, 2021, 36(5): 1102-1117.
[2]	Zhi-Xin Qi, Hong-Zhi Wang, An-Jie Wang. Impacts of Dirty Data on Classification and Clustering Models: An Experimental Evaluation [J]. Journal of Computer Science and Technology, 2021, 36(4): 806-821.
[3]	Jing-Xuan Zhang, Chuan-Qi Tao, Zhi-Qiu Huang, Xin Chen. Discovering API Directives from API Specifications with Text Classification [J]. Journal of Computer Science and Technology, 2021, 36(4): 922-943.
[4]	Jun Gao, Paul Liu, Guang-Di Liu, Le Zhang. Robust Needle Localization and Enhancement Algorithm for Ultrasound by Deep Learning and Beam Steering Methods [J]. Journal of Computer Science and Technology, 2021, 36(2): 334-346.
[5]	Hua Chen, Juan Liu, Qing-Man Wen, Zhi-Qun Zuo, Jia-Sheng Liu, Jing Feng, Bao-Chuan Pang, Di Xiao. CytoBrain: Cervical Cancer Screening System Based on Deep Learning Technology [J]. Journal of Computer Science and Technology, 2021, 36(2): 347-360.
[6]	Xia-An Bi, Zhao-Xu Xing, Rui-Hui Xu, Xi Hu. An Efficient WRF Framework for Discovering Risk Genes and Abnormal Brain Regions in Parkinson's Disease Based on Imaging Genetics Data [J]. Journal of Computer Science and Technology, 2021, 36(2): 361-374.
[7]	Bo-Wei Zou, Rong-Tao Huang, Zeng-Zhuang Xu, Yu Hong, Guo-Dong Zhou. Language Adaptation for Entity Relation Classification via Adversarial Neural Networks [J]. Journal of Computer Science and Technology, 2021, 36(1): 207-220.
[8]	Punit Kumar, Atul Gupta. Active Learning Query Strategies for Classification, Regression, and Clustering: A Survey [J]. Journal of Computer Science and Technology, 2020, 35(4): 913-945.
[9]	Yi-Min Wen, Shuai Liu. Semi-Supervised Classification of Data Streams by BIRCH Ensemble and Local Structure Mapping [J]. Journal of Computer Science and Technology, 2020, 35(2): 295-304.
[10]	Yun-Yun Wang, Jian-Min Gu, Chao Wang, Song-Can Chen, Hui Xue. Discrimination-Aware Domain Adversarial Neural Network [J]. Journal of Computer Science and Technology, 2020, 35(2): 259-267.
[11]	Yang Li, Wen-Zhuo Song, Bo Yang. Stochastic Variational Inference-Based Parallel and Online Supervised Topic Model for Large-Scale Text Processing [J]. Journal of Computer Science and Technology, 2018, 33(5): 1007-1022.
[12]	Tong Shen, Da-Fang Zhang, Gao-Gang Xie, Xin-Yi Zhang. Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems [J]. Journal of Computer Science and Technology, 2018, 33(5): 1056-1071.
[13]	Xian-Hua Zeng, Bang-Gui Liu, Meng Zhou. Understanding and Generating Ultrasound Image Description [J]. Journal of Computer Science and Technology, 2018, 33(5): 1086-1100.
[14]	Qian Wang, You-Dong Ding. A Novel Fine-Grained Method for Vehicle Type Recognition Based on the Locally Enhanced PCANet Neural Network [J]. , 2018, 33(2): 335-350.
[15]	Li Zhang, Xin-Yue Huang, Jing Jiang, Ya-Kun Hu. CSLabel:An Approach for Labelling Mobile App Reviews [J]. , 2017, 32(6): 1076-1089.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 10

[1]	Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[2]	Meng Liming; Xu Xiaofei; Chang Huiyou; Chen Guangxi; Hu Mingzeng; Li Sheng;. A Tree-Structured Database Machine for Large Relational Database Systems[J]. , 1987, 2(4): 265 -275 .
[3]	Lin Qi; Xia Peisu;. The Design and Implementation of a Very Fast Experimental Pipelining Computer[J]. , 1988, 3(1): 1 -6 .
[4]	Sun Chengzheng; Tzu Yungui;. A New Method for Describing the AND-OR-Parallel Execution of Logic Programs[J]. , 1988, 3(2): 102 -112 .
[5]	Zhang Bo; Zhang Tian; Zhang Jianwei; Zhang Ling;. Motion Planning for Robots with Topological Dimension Reduction Method[J]. , 1990, 5(1): 1 -16 .
[6]	Wang Dingxing; Zheng Weimin; Du Xiaoli; Guo Yike;. On the Execution Mechanisms of Parallel Graph Reduction[J]. , 1990, 5(4): 333 -346 .
[7]	Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[8]	Zhao Jinghai; Liu Shenquan;. An Environment for Rapid Prototyping of Interactive Systems[J]. , 1991, 6(2): 135 -144 .
[9]	Shang Lujun; Xu Lihui;. Notes on the Design of an Integrated Object-Oriented DBMS Family[J]. , 1991, 6(4): 389 -394 .
[10]	Xu Jianguo; Gou Yuchai; Lin Zongkai;. HEPAPS:A PCB Automatic Placement System[J]. , 1992, 7(1): 39 -46 .