2 -Edge- Connectivity Augmentation Problems for Directed Graphs

• Item type: SIG Technical Reports(1)
• 公開日: 1989-11-20
• タイトル: 2 -Edge- Connectivity Augmentation Problems for Directed Graphs
• タイトル / 言語: en
• タイトル: 2 -Edge- Connectivity Augmentation Problems for Directed Graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Faculty of Engineering Hiroshima University
• 著者所属: Faculty of Engineering Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Hiroshima University
• 著者名: Masaya, Takahashi; Toshimasa, Watanabe
• 著者名(英): Masaya, Takahashi; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The paper discusses the 2-edge-connectivity augmentation problem for directed graphs which is defined by "Given a directed graph G=(V E) and a cost function c of ordered pairs of vertices of G into nonnegative integers each of which is the cost of an edge from the first vertex of the pair to the second one find a set of directed edges E' of minimum total cost such that the graph G+E'=(V E∪E') is a 2-edge-connected directed graph" where edges of E' connect distinct vertices of V. We show that the unweighted version of the problem that is. c(u v)=c(u' v') for any two ordered pairs (u v) (u' v') of vertices of G and we ask for a solution E' of minimum cardinality can be solved in O(|V|^2(|E|+|V|)^＆ｌｔ；3/2＆ｇｔ；) time.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The paper discusses the 2-edge-connectivity augmentation problem for directed graphs, which is defined by "Given a directed graph G=(V,E) and a cost function c of ordered pairs of vertices of G into nonnegative integers each of which is the cost of an edge from the first vertex of the pair to the second one, find a set of directed edges, E', of minimum total cost such that the graph G+E'=(V,E∪E') is a 2-edge-connected directed graph", where edges of E' connect distinct vertices of V. We show that the unweighted version of the problem, that is. c(u,v)=c(u',v') for any two ordered pairs (u,v), (u',v') of vertices of G and we ask for a solution E' of minimum cardinality, can be solved in O(|V|^2(|E|+|V|)^＆ｌｔ；3/2＆ｇｔ；) time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1989, 号 98(1989-AL-012), p. 53-60, 発行日 1989-11-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会