• DocumentCode
    1621760
  • Title

    3-edge-connectivity augmentation problems

  • Author

    Watanabe, Toshimasa ; Narita, Takanori ; Nakamura, Akira

  • Author_Institution
    Fac. of Eng., Hiroshima Univ., Japan
  • fYear
    1989
  • Firstpage
    335
  • Abstract
    The NP-completeness and an O(V3) approximation algorithm are shown for the three-edge-connectivity augmentation problem: given a complete graph G=(V, E), a spanning subgraph G0=(V, E\´), and a cost function c of E into nonnegative integers, find E"⊆E-E\´ of minimum total cost such that the graph (V, E\´ ∪ E") is simple and three-edge connected. It is proved that the problem is NP-complete, even if G0 is two-vertex connected, and that the approximate solution obtained in this case has a total cost less than that of a certain spanning tree determined by G0
  • Keywords
    approximation theory; computational complexity; directed graphs; trees (mathematics); NP-completeness; approximation algorithm; cost; cost function; minimum total cost; nonnegative integers; spanning subgraph; spanning tree; three-edge-connectivity augmentation problem; two-vertex connected; Approximation algorithms; Computational complexity; Cost function; Electrocardiography; Polynomials; Tin; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Circuits and Systems, 1989., IEEE International Symposium on
  • Conference_Location
    Portland, OR
  • Type

    conf

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