TY - GEN

T1 - Two phases algorithm of transport network design problem

AU - Zhang, Jianghua

AU - Kong, Guangwen

AU - Zhu, Daoli

AU - Han, Qiang

PY - 2007

Y1 - 2007

N2 - The transport network design problem deals with how to add or improve some edges on an existing transport network using quantitative analysis method. This paper put forward two phases algorithm of transport network design based on network optimization, which concludes enumerating all cut sets and resolving single-side domination set problem of weighted bipartite graph. Firstly, a single-side domination set problem of weighted bipartite graph is defined, along with the corresponding algorithm. Then two phases algorithm of transport network design is constructed by combining the algorithm mentioned above with the algorithm enumerating all cut sets. Further, the complexity of algorithm is analyzed, and it is proved that the algorithm could end in finite step. Finally, a numerical example is presented to show the efficiency of algorithm.

AB - The transport network design problem deals with how to add or improve some edges on an existing transport network using quantitative analysis method. This paper put forward two phases algorithm of transport network design based on network optimization, which concludes enumerating all cut sets and resolving single-side domination set problem of weighted bipartite graph. Firstly, a single-side domination set problem of weighted bipartite graph is defined, along with the corresponding algorithm. Then two phases algorithm of transport network design is constructed by combining the algorithm mentioned above with the algorithm enumerating all cut sets. Further, the complexity of algorithm is analyzed, and it is proved that the algorithm could end in finite step. Finally, a numerical example is presented to show the efficiency of algorithm.

KW - Heuristic algorithm

KW - Network optimization

KW - Single-side domination set

KW - Transport network design problem

KW - Weighted bipartite graph

UR - http://www.scopus.com/inward/record.url?scp=38049048210&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049048210&partnerID=8YFLogxK

U2 - 10.1109/WICOM.2007.1603

DO - 10.1109/WICOM.2007.1603

M3 - Conference contribution

AN - SCOPUS:38049048210

SN - 1424413125

SN - 1424413125

SN - 9781424413126

SN - 9781424413126

T3 - 2007 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2007

SP - 6533

EP - 6536

BT - 2007 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2007

PB - IEEE Computer Society

T2 - 2007 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2007

Y2 - 21 September 2007 through 25 September 2007

ER -