Abstract | ||
---|---|---|
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 complete bipartite 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. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1109/FSKD.2008.210 | FSKD (4) |
Keywords | Field | DocType |
generality graph binding number,binding number,binding number computation,multi-product graph,multiple cartesian product graph,compiler,complete bipartite graph,maximum network flow algorithm,generality graph,special graph,polynomial algorithm,graph-based binding algorithm,completebipartite graph,multiproduct graphs,product graph,graph theory,computer science,polynomials,product graphs,cartesian product,time complexity,minimum cut,network flow,bipartite graph,algorithm design and analysis,radiation detectors | Discrete mathematics,Combinatorics,Line graph,Graph property,Computer science,Null graph,Pathwidth,Lattice graph,Butterfly graph,Graph (abstract data type),Voltage graph | Conference |
Volume | ISBN | Citations |
4 | 978-0-7695-3305-6 | 0 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Congying Han | 1 | 17 | 4.07 |
Guoping He | 2 | 91 | 13.59 |
Hua Duan | 3 | 110 | 19.58 |
Xuping Zhang | 4 | 39 | 8.00 |