Augmentation of undirected graph to a R-edge-connected graph based on hops-constraint

Li Shan Sun; Zhi Yang; Hai Long Chi

Augmentation of undirected graph to a R-edge-connected graph based on hops-constraint

Li Shan Sun^*
, Zhi Yang
, Hai Long Chi

^*Corresponding author for this work

School of Electrical Engineering and Automation

Harbin Institute of Technology

Research output: Contribution to journal › Article › peer-review

Abstract

A heuristic iterative algorithm is presented to solve the problem of undirected graph's R-edge-connectivity augmentation based on hop-constraint. Using this method, an initial R-edge-connectivity graph is formed and the cost of new added edges is reduced by edge-exchanging and edge-replacing. Finally some edges meeting the demand of hops are added and an optimal or a better graph is obtained when the cost is reduced by edge-shifting and edge-deleting.

Original language	English
Pages (from-to)	766-768+811
Journal	Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology
Volume	36
Issue number	6
State	Published - Jun 2004

Keywords

Edge-connectivity
Hop
Network planning
R-edge-connectivity augmentation

Cite this

@article{c0a811a8e58a4187bb8133aa49ef5d50,

title = "Augmentation of undirected graph to a R-edge-connected graph based on hops-constraint",

abstract = "A heuristic iterative algorithm is presented to solve the problem of undirected graph's R-edge-connectivity augmentation based on hop-constraint. Using this method, an initial R-edge-connectivity graph is formed and the cost of new added edges is reduced by edge-exchanging and edge-replacing. Finally some edges meeting the demand of hops are added and an optimal or a better graph is obtained when the cost is reduced by edge-shifting and edge-deleting.",

keywords = "Edge-connectivity, Hop, Network planning, R-edge-connectivity augmentation",

author = "Sun, \{Li Shan\} and Zhi Yang and Chi, \{Hai Long\}",

year = "2004",

month = jun,

language = "英语",

volume = "36",

pages = "766--768+811",

journal = "Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology",

issn = "0367-6234",

publisher = "Harbin Institute of Technology",

number = "6",

}

TY - JOUR

T1 - Augmentation of undirected graph to a R-edge-connected graph based on hops-constraint

AU - Sun, Li Shan

AU - Yang, Zhi

AU - Chi, Hai Long

PY - 2004/6

Y1 - 2004/6

N2 - A heuristic iterative algorithm is presented to solve the problem of undirected graph's R-edge-connectivity augmentation based on hop-constraint. Using this method, an initial R-edge-connectivity graph is formed and the cost of new added edges is reduced by edge-exchanging and edge-replacing. Finally some edges meeting the demand of hops are added and an optimal or a better graph is obtained when the cost is reduced by edge-shifting and edge-deleting.

AB - A heuristic iterative algorithm is presented to solve the problem of undirected graph's R-edge-connectivity augmentation based on hop-constraint. Using this method, an initial R-edge-connectivity graph is formed and the cost of new added edges is reduced by edge-exchanging and edge-replacing. Finally some edges meeting the demand of hops are added and an optimal or a better graph is obtained when the cost is reduced by edge-shifting and edge-deleting.

KW - Edge-connectivity

KW - Hop

KW - Network planning

KW - R-edge-connectivity augmentation

UR - https://www.scopus.com/pages/publications/3142784260

M3 - 文章

AN - SCOPUS:3142784260

SN - 0367-6234

VL - 36

SP - 766-768+811

JO - Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology

JF - Harbin Gongye Daxue Xuebao/Journal of Harbin Institute of Technology

IS - 6

ER -

Augmentation of undirected graph to a R-edge-connected graph based on hops-constraint

Abstract

Keywords

Other files and links

Fingerprint

Cite this