2020-04-09T08:13:18Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:000326662020-04-01T00:33:29Z01164:02592:02721:02722
2 -Edge- Connectivity Augmentation Problems for Directed Graphs2 -Edge- Connectivity Augmentation Problems for Directed Graphsjpnhttp://id.nii.ac.jp/1001/00032666/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32666&item_no=1&attribute_id=1&file_no=1Copyright (c) 1989 by the Information Processing Society of JapanFaculty of Engineering Hiroshima UniversityFaculty of Engineering Hiroshima UniversityMasaya, TakahashiToshimasa, WatanabeThe 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）198998(1989-AL-012)53601989-11-202009-06-30