Two phases algorithm of transport network design problem

Jianghua Zhang, Guangwen Kong, Daoli Zhu, Qiang Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2007 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2007
PublisherIEEE Computer Society
Pages6533-6536
Number of pages4
ISBN (Print)1424413125, 1424413125, 9781424413126, 9781424413126
DOIs
StatePublished - 2007
Event2007 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2007 - Shanghai, China
Duration: Sep 21 2007Sep 25 2007

Publication series

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

Other

Other2007 International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM 2007
CountryChina
CityShanghai
Period9/21/079/25/07

Keywords

  • Heuristic algorithm
  • Network optimization
  • Single-side domination set
  • Transport network design problem
  • Weighted bipartite graph

Fingerprint Dive into the research topics of 'Two phases algorithm of transport network design problem'. Together they form a unique fingerprint.

Cite this