• DocumentCode
    2663834
  • Title

    An approach to robust network construction from graph augmentation problems

  • Author

    Watanabe, Toshimasa ; Higashi, Yasuhiko ; Nakamura, Akira

  • Author_Institution
    Fac. of Eng., Hiroshima Univ., Japan
  • fYear
    1990
  • fDate
    1-3 May 1990
  • Firstpage
    2861
  • Abstract
    The problem of constructing a robust communication network by adding a minimum-cost set of new links is discussed. The problem is formulated as the k-edge-connectivity (k-vertex-connectivity, respectively) augmentation problem for a specified set of vertices. For k=2, an O(|V|2) (O|V|3) approximation algorithm is proposed, with the worst approximation no greater than twice (less than four times) the optimal
  • Keywords
    graph theory; telecommunication networks; graph augmentation problems; minimum-cost set; robust network construction; Approximation algorithms; Bridges; Communication networks; Cost function; Joining processes; Robustness; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Circuits and Systems, 1990., IEEE International Symposium on
  • Conference_Location
    New Orleans, LA
  • Type

    conf

  • DOI
    10.1109/ISCAS.1990.112607
  • Filename
    112607
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2663834