Third International conference on advances in communication, network and computing

Research Article

Diameter Restricted Fault Tolerant Network Design

  • @INPROCEEDINGS{10.1007/978-3-642-35615-5_19,
        author={P. Saxena and Sangeeta Sabharwal and Maneesha},
        title={Diameter Restricted Fault Tolerant Network Design},
        proceedings={Third International conference on advances in communication, network and computing},
        keywords={Diameter k-connected Network Fault Tolerant Eccentricity},
  • P. Saxena
    Sangeeta Sabharwal
    Year: 2012
    Diameter Restricted Fault Tolerant Network Design
    DOI: 10.1007/978-3-642-35615-5_19
P. Saxena1, Sangeeta Sabharwal2, Maneesha2
  • 1: Jawaharlal Nehru University
  • 2: Netaji Subhas Institute of Technology


Low transmission delay, high fault tolerance and low design cost are the three main properties of any network which are best described by its topology. Transmission delay can be decreased by restricting the diameter of the network. Very few methods in literature have considered the importance of the diameter of the network to decrease the transmission delay. Fault tolerance in the network depends on the number of disjoint paths between a node pair. Designing a k-connected fault tolerant network subject to connectivity and diameter constraint at minimal cost is a NP hard problem. In this paper, an efficient constructive heuristic algorithm is proposed for designing a k-connected network while optimizing the cost of the network subject to the connectivity and diameter constraints. Diameter of resultant network would be of two links regardless of network size to get the speed comparable to complete connected network at low cost. Effectiveness of the proposed approach is also evaluated using different examples.