A Binding Number Computation of Graph
Congying Han, Guoping He, Hua Duan, Xuping Zhang · 2008
Graph-based binding algorithm is very popular for a retargetable compiler in computer science. Binding number, one indicator to better understand graph, is an important characteristic quantity of graph. Constant work have been done on binding number computation by many researchers for some special graphs, such as product graphs, multi-product graphs, multiple cartesian product graph of completebipartite graph. This paper is meant to present a polynomial algorithm of the generality graph binding number through the maximum network flow algorithm. We convert binding number computation into calculating the capacity of a minimum cut by constructing directed network with some parameters based on the transformation idea from the least ratio to the least difference. In the latter part,the time complexity of the polynomial algorithm is analyzed and given.