http://swrc.ontoware.org/ontology#TechnicalReport
2 -Edge- Connectivity Augmentation Problems for Directed Graphs
ja
Faculty of Engineering Hiroshima University
Faculty of Engineering Hiroshima University
Masaya Takahashi
Toshimasa Watanabe
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.
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.
AN1009593X
情報処理学会研究報告アルゴリズム（AL）
1989
98(1989-AL-012)
53-60
1989-11-20