DocumentCode
3138857
Title
Graph Augmentation Problem with Diameter Requirements
Author
Ishii, Takuro
Author_Institution
Grad. Sch. of Econ., Hokkaido Univ., Sapporo, Japan
fYear
2012
fDate
5-7 Dec. 2012
Firstpage
393
Lastpage
398
Abstract
In communication networks, the distance between two nodes is one measure of transfer delay between them. Thus, it is required that the diameter of the network, which is defined as the maximum distance between every two nodes in it, is relatively small. This paper surveys the computational results on graph augmentation problems which model network design problems with diameter requirements, initiated in [F. R. K. Chung and M. R. Garey, "Diameter bounds for altered graphs," J. Graph Theory, vol. 8, pp. 511-534, 1984].
Keywords
delays; network theory (graphs); telecommunication networks; communication networks; diameter requirements; graph augmentation problem; network diameter; transfer delay; Approximation algorithms; Approximation methods; Delay; Joining processes; Optimized production technology; Polynomials; Vegetation; algorithms; diameter; edge addition; graphs;
fLanguage
English
Publisher
ieee
Conference_Titel
Networking and Computing (ICNC), 2012 Third International Conference on
Conference_Location
Okinawa
Print_ISBN
978-1-4673-4624-5
Type
conf
DOI
10.1109/ICNC.2012.75
Filename
6424601
Link To Document