λ-辺連結グラフにおける指定点集合の（λ+1）-辺連結化のための2-近似アルゴリズムFSA+1

全文

(1)アルゴリズム 87−４（２００２．１１．８）.

(2) "!$# - %&'( 2-35) 47IK*,J 698 +: -/;=. < >@0 ?B1A 2 C=DFFSA+1 : H E G WKJ <Y<5X9LNZRM9L9LNM\M@[@OQ]NPR^9MT_@SHV=URMRV ` a b Rx s¡{cH¢kd=£yeT¤ fTt¥gihkw§jk¦ ¨Rlnm$©=oqpsª9rutv«{hx¬¥wy `R¦ z{eYf5g|h~}®yj¯ ln=moq°5p~±³}r ²YN´H9µ@ ¶ Yt¸ ·¹lºm¼»½h~m° }¾r¿tjÀ·¹lºµ »Áh~}Â\rÃ °³pÄ { w ln£ ·$Å³ÊÏÆÇtTr Ì ¶ h~}$wyÈ³âäÉãkÊvtve=ËsfYlºÌ5gæÅåsÍÎlnmÏhçÍÐ}¾ÍÎrèpÑ®ÍÒrâ=ÓYé=;9ß w °êYÔ5ëÕHÓ@Ö×k;yìNØ{í@ÙvÚRî Û £ ß °5± ®ÝÜTÞNß t¸à9à tá·³jÀ·¹lº»Áh~}r ï/!# -Edge-Connect a A 2-Approximation Algorithm FSA+1 to Specified Set of Vertices in a -Edge-Connected Graph : : A W I a b hBj7ln¦m$oqpsr h~}ðjBlnmoqp~}ñr h iFm pËslº ¦ ln·èÅäÆÇr ·¹lnm¼h~»Á} h~}r¿jÀ·¹ló$»Áh~}Âr ÌiÅ@ÍÒmÑ·³ÍÎ pjÀÍòr ·¹lº»Áh~}Âr Ì åvlºh~}r -. ,. ,. Email: taoka,watanabe @infonets.hiroshima-u.ac.jp, [email protected] ,. [Abstract]. -. ECA-SV. :. ( ECA-SV) 2-. FSA+1. Satoshi Taoka , Toshiya Mashima , Toshimasa Watanabe Graduate School of Engineering, Hiroshima University Faculty of Infrastructural Technologies, Hiroshima International University Email: taoka,watanabe @infonets.hiroshima-u.ac.jp, [email protected]. , a subgraph of , a specified set , and [Abstract] Given an undirected graph a cost function : , we consider the -edge-connectivity augmentation problem for ( ECA-SV). The paper proposes an time 2-approximation algorithm FSA+1 for ECA-SV for the case when , where and is the time complexity of constructing a structural graph of .. 1. Introduction. ¦. ¦. [Problem definition] The -edge-connectivity augmentation problem for a specified set of vertices (W- ECASV) is defined as follows: “Given an undirected graph , a spanning subgraph of , a specified set of vertices and a cost function : (nonnegative real numbers), find a set of edges, each connecting distinct vertices of , of minimum total cost such that for ,” where means that has at least edge disjoint paths between any pair of vertices in . Costs for is denoted as for simplicity. with is denoted as . The -vertex-connectivity augmentation problem for a specified set of vertices (W- VCASV) is similarly defined if we consider “internally disjoint paths” instead of “edge disjoint paths”. For simplicity, let ECA-SV denote W- ECA-SV unless otherwise stated in this paper. ECA-SV with is denoted simply as ECA, called the -edge-connectivity augmentation problem. The problem is called the unweighted version, denoted by UW- ECA-SV, if has multiple edges connecting and for any and any edge cost is unity.. 3. 14 8. 13. 3. 1. 4. 12 3. 2. 5. 5. 6. 7h jBlnmoqpsr h~}çjFlºm$oqp~}ñr h Y ï m ppYôö5 p~} põ} èm \h j7¹· lnmvlnm$»½oqh~ps}rr j ¹· lº»Áh~}rj hõ}õj n l $ m q o ~ p ñ } r h~}ùÅähõp~} } újlnm$oûpõ}¹üy¦ p~} r ·¹lº·¹lº»Áh~»Á}÷h~ÅH} ýrþp~øk} rð¦ ø¦ Àp ökp~} p~} rºr lÂÿ o rp u ó l l ÿ o p

(3) ulÿ·¹olnh r r ¦ ·¹lº»Áh r {j m ¦ ¦. ¦. ¦ ¦ ¦ N j§m ÿ ¦ ÿ o h m. ¦. . . By “an -approximation algorithm” we mean that it produces a solution whose total cost is no more than times the optimum. This solution is called “an approximate solution,” and we say that the performance ratio of the algorithm is : this statement is simply represented as .. . xj. . . 11. 7. 3. 10. 5. 5. 9. 8. 6. and a spanning subgraph Figure 1: with , where black vertices are in , solid lines are edges in , (fine or bold) dotted lines are ones in , numbers shown beside edges are costs, and bold dotted lines denote an optimum solution , of total cost 25, for ECA-SV.. Table 1: Summary of NP-completeness results, where is a complete graph of vertices Problem 2ECA 3ECA ECA. Ref. [4] [27] [26]. . . tree. . no edges. Costs Comments or or. .

(4). ·¹lnpm¼ »Áhõ}Ârõj! Çlºj§·¹r. Example 1 Fig. 1 shows an example of ECA-SV, where . Also shown is an optimum solution .. ¦. [Applications and related results] The problem has application to designing robust networks: a -edgeconnected network can survive communication lines’ failure.. ¦. ¦yö|Æ. Some related results on ECA and summarized in Tables 1 and 2.. 1 −25−. ¦. ECA-SV are.

(5) Table 2: Results concerning optimum, approximate or heuristic solutions, where Problem. Ref.. 2ECA. [4]. #%$ 2 if '&( 3 if '&() 2 if 1 '&. Time. Space. Yj|ÍÎmvÍ . and. j|ÍÒpÑÍ. ". Comments. * ,+.- * /+0- 2ECA [14] 2 /3546+87:9<;+ 2 /* +6463 3ECA FS[27] 2 minimum-cost arborescence 2 /+>= / +0- ECA [15] 2 packing arborescence 2 +.,3?4@7:9<;.+ 7:9<;+ 2 /* +66 4 3 3ECA [28] unbounded max weight matching* 2 /+ = 7A9<;+ * /+ - 2 /+>* =B7A9<;+ ECA [24, 25] unbounded weight matching* * //+0+ -- .max 2ECA-SV [23] 2 reduction to 2ECA[4] ( ,+ - * /+ - 1 CD0&E ,,max 2 /+ = 7A9<;+ 3ECA-SV [29] unbounded weight matching* 2 LECA** [12] 2 G : F I H , F L J M K F N : F O QP if 2 - + - 4 +.R 3S7A9<;.7:9<;.+ LECA** [8] if &( U T 2 /+8VXWAY'Z +.[\3^]_ 4`+ 4`+ b- a T '&( 4c-J 4edfdgdh4ij J LECA** [10] * Four heuristic algorithms are proposed, and the one using maximum weight matching has highest capability. ** LECA (local edge-connectivity augmentation problem) contains ECA-SV as a subproblem.. ·¹lnhç}ñr@j· ·F· ø Æ h~} · ln·TnÅ m½r. ln·¸Å ÇÆ r ·¹ló$»Áh~}Âr. [Subjects and main results] In this paper, is denoted as for short. For ECA-SV with , (1) and (2) are the main results, where since if then the problem we assume is optimally solved by using an algorithm for finding a minimum-cost spanning tree. (1) The recognition version of ECA is NP-complete even if , is -edge-connected and edge costs are either 1 or 2. (This part is omitted because of space limitation in this paper.) (2) A 2-approximation algorithm FSA+1 for ECA-SV with is proposed, based on a minimum-cost arborescence algorithm. Its time complexity (space complexity, respectively) is ( ) if is even, or ( ) if is odd, where is time complexity of finding a structural graph of given graph . (The early version of this paper appeared in [16, 24].). w . h=öew lÿ o r. ÿ. . h. edges incident to . is called a separator of , or in particular a -separator if and are disconnected in . A minimum separator of is a separator of minimum cardinality among those of , and is the edge-connectivity (denoted by ) of in case ; particularly such is called a minimum cut (of ). (For a minimum separator , is the vertex-connectivity if .) It is called also a -cut if . If then the element of is called a cutpoint in case or a bridge in case . A minimum cut is often denoted as , where is a partition of such that . If no confusion occurs then is simply represented as . We say that a cut separates if and only if and : is called a -cut or a - -cut if . A minimum -cut is defined similarly to a minimum cut.. h h Í}w¿Í wÀ§p ·¹lnh r h wÀ§p mkjÆ h ~ùlnh r wôm w :Í w¿Í ¦ Í}w¿Íèj ¦ Í}w¿Íèj wôÆ m w ln·TÅ ÆÇr ·¹lºh~}ñr@j·¹lº»Áh~}Âr w§ôp lDwRoj »½a½h lÿ r o r6pQ Í$5ÿü |w§Tôo p |yb m ËslºÌÀÅËsÍÒlºpÑÌ|Íòr ÅkËvÍÎmÏl ÍÒÍÐmÏÍÒpÍ ÍòÅir ÍÎËspÏlÍÒrÍÎmsÍ oá· ÅxÍÎpÏÍÒr · Ì lDToGr Nj lDRo¸=»ÁDl Ths or @j r wFj Dl Ro är h~} ¦ Í}w¿Í¿j\¦ ÿ q o r ÿ h j lnm lnh rnoÁpslnh rºr ô h j n l $ m q o s p r r ÿ l ÿ o r h j lºmÏl hsrºo<põl hèrºr ÿ h j lnq m$ÿ _o o p~srr q ÿ o sr q oÿ r v t u l q ÿ o 'r ÿ t l r t lr ÿ ÿ h lÿ o r h } ÿ ÿ h ÿ } ·¹lÿ o »Áh r ·¹ÿ lo ÿ o r r h ÿ l ·¹fl w$»Áhsw§rð yj mx@z,{¹a ·¹wïlÂÿ jo »Ám hsrðÍ ÿ o Swþb ÿ ÿ ·¹lnh r wämkü5p h hx|ö w w h 2. ·§jlk. Preliminaries. Technical terms not specified here can be identified in [2, 21]. is often An (undirected) graph denoted as , and an (undirected) edge between and is denotes as . A directed graph is often denoted as , and a directed edge from to is denoted as . The degree of a vertex is denoted as , or simply : is often called a degreevertex. A path from to in is referred to as a -path. We consider a pair of multiple edges as a cycle of length 2. A connected component (is simply called a component). Let or simply denote the maximum number of edge-disjoint -paths of . We represent as for a set of vertices . If then we simply represent as , which is called the edge-connectivity of . Let be any minimal set such that (a graph obtained by deleting all element of from ) is disconnected where deleting a vertex removes all. . w. A directed path from to is referred as a path, and we say that is reachable from . An arborescence is a directed acyclic graph with one specified vertex, called the root, having no entering edges, all other vertices having exactly one entering edge and they are reachable from the root. A minimum-cost arborescence is an arborescence of minimum total cost. For an arborescence with the root , a graph consisting of edges such that the edges are contained in the arborescence is called a reverse arborescence rooted at . If there is a -path in a (reverse) arborescence, is an ancestor of and is a descendant of . For a reverse arborescence , is called a leaf if there are no ancestors of in . Suppose that is not an ancestor of and is not an ancestor of in a reverse arborescence with the root . Then a nearest common descendant of and is a common descendant of and such that it is the nearest among all such common descendants. A cactus is an undirected connected graph in which any pair of cycles share at most one vertex: each shared vertex is a cutpoint. An edge of a cactus is called a cycle edge if it is contained in a cycle; otherwise it is called. 2 −26−.

(6) 8. {14} {13}. k’. k" {12}. d a {1}. 3. f. j {11}. i. n. {10} 6. {6} 5. {8}. {5}. 3. b {2,9}. l. e. m. 5. {7}. h. 3. g. h. jh~} lº rjåslnh~}Âr h~} h~} p öHp~} p. p > lÿ r ÿETm t l r¿jkÆ } t l }ýr j h r s å n l lnm$oûpvr ·¹lnhh rNj· åslnh h r j ËvlnÍÎmÏÍÒr · · åslnh r ymslnh rä · ms lnåslnh rºr mÏmÏlºlºåshslnr h rºrõöïmslnh r " s å n l h r Ësl ÍÎmÏÍÎ pÑÍÒr · Ësl ÍÎpÏÍñÅ³·o ÍÎmÏÍ}½l ÍÎmÍ}Ç·¹rór · v åvlº· hsr ·¹lnå lnh rºrj Æ · ·¹lnå lnh rºrT j · ¦ ·¹lnh~}ýr j·¹lº»Áh~}ñr. Figure 2: A graph (to be constructed in Step 2 of FSA+1) and a structural graph ( ) of , where black vertices are in , edges in are denoted by solid lines with weight , and (fine or bold) dotted lines are edges in (bold dotted lines are edges in constructed from an optimum solution ), and for each is shown in braces a tree edge. A leaf of a cactus is either a vertex with or with included in a cycle. A structural graph of a given graph with edge-connectivity is a representation of all minimum cuts of (Fig. 2). is an edge-weighted cactus of nodes and edges such that each tree edge has weight and each cycle edge has weight . Particularly if is odd then is a weighted tree. There is a one-to-one function , and any vertex of is called an empty node to which has no corresponding vertices (see , , in Fig. 2). It is shown that can be constructed in time [13] or time [5]. Note that if is even then replacing each tree edge by a pair of multiple edges of weight preserves the properties of structural graphs and makes their handling easy because the resulting graphs have no bridges. This graph, as well as a tree in the case where is odd, is called a modified cactus. In this paper, denotes a modified cactus unless otherwise stated. Note that if is odd and if is even. 3. A 2-Approximate Algorithm for W- ECA-SV with. · nl ·ÑÅÆÇr ln·ÅHÆÇr h~} ·¹ln·¹hçlnh~}ñrv}Ârõj\j§·¹·¹ló$lº»Áh~»Áh~}Âr }rçj ·¹lnå·¹lºlnh~»Á}ñhõrórÝ}Âr j Æ ·¹lº»Áh~}r ·¹lnåså lnlnh h~} }Âr rºrj¡ åslnh~}Âr ¢£ ·¹lº»Áh~}r ¢¤£¡¥ ·¹lº»Áh~}Âr ¦ l ÍÎmÍ oÇr ·¹lnhç}ñr j7Æ. ·¹lnhç}ñr¸j§. SV and UW-3ECA-SV for the case with . These four algorithms are outlined as follows. First, with is transformed a given graph into a graph such that a minimum solution to ECASV for , and is a minimum solution to ECA for , and , and vice versa. For such a graph W-2ECA (UW-3ECA or W-3ECA, respectively) is time algorithm of [4] solved by means of an (an time algorithm of [30] or some heuristic algorithms proposed in [24, 25, 28]). Then a 2approximate solution (an optimum one or a heuristic one) is obtained. The algorithm of [4] is based on a minimum-cost arborescence algorithm [7]. Our algorithm FSA+1 is based on a minimum-cost arborescence algorithm [7] and utilizes the algorithm of [14], instead of [4], for solving 2ECA. The algorithm FSA+1 is outlined as follows. First, we con( ) of struct a structural graph by the algorithm in [5, 13] (see and of Fig. 1 and of Fig. 2). According to the construction, we obtain a graph , a specified vertex set , a cost function and a backpointer (see Fig. 2). Secondly, is changed into a simple graph by deleting will be constructed as multiplicity, and then a tree follows (see Fig. 3): for each cycle that is remaining in this simple graph, a new vertex is added, each vertex on and are connected by an edge, and then all edges of are deleted. Let denote the resulting tree. Next, we choose some vertex as the root of , and direct every edge of toward . Note that becomes a leaf in to be constructed later. Let denote the resulting directed graph (see Fig. 6). Some modification of and will be done. From , and , we obtain and that are a supergraph containing and the associated cost function, respectively. And then, we construct a maximal subgraph , which is a tree, from such that , , and for any leaf of . According to the construction, we obtain a supergraph containing , , the associated cost function and a backpointer from and (see Fig. 7). Finally we find a minimum-cost arborescence of with respect to (see Fig. 8), and an approximate solution of is obtained from . [Description of FSA+1] We first present Procedure REMAKE that changes a modified cactus ( ) into a spanning tree .. h ~} ·¹lnh~}ýr¥j¨¢¼öÆ ~ h } h h } h ~ h ~ } õh } Ësl ÍÎmÏÍºÅ5ÍÎpÏÍÒr ¦sl ÍÒmÍ o r. {3}. c. k. 5. {4}. ¢. ¢. hõ} j|lºm$oqp~}ñr h h~} jln1m oqp~} r j åsh lnhç}r hõ} j lºr ª«úp h öx jæp~} lnm oÁ pp r p ö@p~} © h } h~}¬ . . B®. ~h }¬ h } ¬ h }¬ j lnm o_pK}¬ur ¬ .p ¬h hú }¬ h } ¬ j lnm ¬ o_pK}¬ur pK} ipK}¬ ÿ(@s h } h ª h ¬ h h~} . h~}¬. B®. h~}¬ | h h ¬ j lºm ¬ o<p ¬ r h }¬ h } jlºm _o pK\} r m \m ¬ ÿ hõ} p ú ¬ ¯>°j lnm ¬ <o p }¬÷r p }¬ ö p } hõ} j åslnh~}Âr. In this section, we propose a 2-approximation algorithm FSA+1 for ECA-SV with . ECA-SV for with can Procedure REMAKE; be reduced to 2ECA-SV or 3ECA-SV for . Since /* Input : . Output : . */ if is odd and if is even, we consider 2ECA-SV or 3ECA1. If is odd then and stop. SV for by setting if is odd, and 2. Delete multiplicity of edges in , making it simif is even. ple. Then find all cycles (each being a 2-ecc of ) For W-2ECA-SV, [23] proposed an time 2by a depth-first-search. approximation algorithm for the case with . 3. For each cycle , add a dummy vertex , connect [23] proposed four heuristic algorithms for W-3ECAto every vertex on and delete all edges 3 −27−. ~h }¬ hõ} jlnm oÁp~} r ~h }¬jlºm ¬ oÁp~¬} r · h~}¬C£ h~} ~h } õh } ± ® ®± lÂÿ o r.

(7) k’. d. k" q. a. c. p. l. u. e. m. k o. b. f. j. v. n. i. r. (2). g. h. h~}¬. r. (1). h~}. t. Figure 3: A tree constructed from in Fig. 2 by procedure REMAKE. A square denotes a dummy vertex. v. r. u r. (3) C. t vi n(Ci)-1. vi0. vik. vi1. vi6 vi5. vi4. vi3. vi2. v. j. .... vij u. ql qr. p½Ó fÔ. Figure 5: Schematic explanation of a set of edges of FSA+1: (1) Case 6.2(a), (2) Case 6.2(b1), (3) Case 6.2(b2).. ¶µ circuit Q² ² ® \² · B³² in . 8 8 8 k’ d 5 8 8 ¬ ¬ be the resulting graph and k" q 8 5 3 5 a root c e be the set of dummy vertices in ¬ (Fig. 3). ¹º 3 m 3 k 55 5 called the root of . FSA+1 chooses a vertex 6 p 5 o 3 3 l b 5 Suppose has at least one cycles whose length is more f j 5 than 2. Let Q² , »¼½»¾ , be cycles in . For each cy6 5 n cle Q² , let 1²³ the vertex which is nearf¿² denote 5 i 3 5 6 5 ³ est from the root , and ² is called the starting vertex of 53 g 5 B ³ h ² . Note that ² is the first visited vertex in ² when we 5 execute the depth first search starting from in Àµ ®.Á We 5 · number the vertices of Q² as B³² ² ²o <´_´<´ ² ¬ _p ¬ and a directed tree clockwise, where fQ² denotes the length of Q² (see Figure 6: A graph ¬ Å Ä ¬ <p ¬ , where solid arrows are edges in p ¬ with ¬ 4). Let Â0² DÃ denote the set of vertices ² through Fig. any vertex È 1 , ¬ fÔ k for any ÔIep ¬ , and (fine or bold) dotted lines ²Æ clockwise on ² for ÃÇ» . ÅFor are edges in p ¬ |p ¬ (bold dotted lines corresponds to q ²É r Å²É ÊÂ ² DÃ let us denote p ² DÃ (see Fig. 5(3)), where all self-loops are deleted. Note edges in ). Â ² DÃ . These that if kÌËÍÃe» ÇËÍ f ² then B³² Î DÐ (see Fig. 2). Let ? f notations are used in constructing ¬ and . . Algorithm FSA+1; ¬ ¬ from¸ by using 3. Construct a tree ¬ /* Input: A graph , a subgraph REMAKE (see Fig. 3). /* The set of dummy of , a specified set with vertices in ¬ is obtained. */ , and a cost function 8 . */ as the root then choose 4. If ¬ has any leaf /* Output: An edge set such that . Otherwise, choose any leaf ¬ , find any . */ vertex ±n s that is nearest from in ¬ , and let ( 1. Construct a structural graph ± be the root . ¬ <p ¬ from ¬ ) of by the algorithm in [5, 13]. 5. Construct a directed tree ¬ , and as follows. 2. Construct by directing each edge of ¬ toward . ¬ <p ¬ , a cost funcFirst, £ edge DÏ ÑÐ E 6. Define a directed graph ¬ . Then, for each ½£ DÏ ÑÐ , set £ , tion ¬ sp ¬ and backpointers ª ¬ p ¬ `£ DÏ ÑÐ , where Ò Ï and and ª as follows (see Figs. 5 and 6):. a l o rnoûl o nr o Îo l o r b h~} hõ}jklnm oÁp~} r ~h } h~} Æ hõ} YmÏl r 4: 1²³ ² ² ²o _´,´,´ of . Let ¬ ¸. Figure. A. o o o o. h~}. h~}. h } l qjkr¿j lnm o ól oq¦ þr l r ï¦ ÿ H m l oq¦ »ºÿ rÝja o ÿ Í l oq¦ r b p §¦ ¿l r h h l oq¦ r l b ùr ln·¹m$lnm¼oûpõ»Á}ýh~r }r jh · h jlnm|oqpsôr m ùp ·¹ lº»Áh~h~}}{rÝjj h} ~ p } / ô p \ ö ~ p } ·¹lº»Áh~}ùÅäp~} ýrKø·vÅHÆ åslnh~}Âr hhõ} jlnm oqp r h } j lºm oqp } r j pöáp~ul} pÿ o r p ,p~l} p o üþr a lÂÿ o r b ÿæ j lÂÿ o l r r l uo l ¹r o ¹j r 4 −28−. } r h }jQlnm o r } ö } j lºrsj a l rÏÍ h~}vj lºm oqpõn} r h~} h~} T 7m h~} N h~p~}} jlºm o } r hõ} h jklnm o r p.

(8) d. 8 8 8. a k. 8. root. 3. 3. 8 5. p. l. 5. j. o. b. i. 6. 5 5 5. m 3 3. k. e. 55 3. a. j. l. 0. 3. b. m. o. 0. i. 0. 3. e 5. f. 0 5. n 6. 0. p 5. 5. 5 root. 3. f. 5. 5 5 5. d. n 6. 0. h. 5. ¯° j o<p ° r n l m õ p } j p ö n l ç p } ü ½ a f l t ½ o ¦ ¾ } n r û o D l à _ o ¹ ¾ n r b ¯'° h~} jBlnm o<p } r h p } jQ lflºÔqm rK o_jyp k r Ô¤Sp } ~ p } ú À j T p ¸ ö n l ~ p } Ï ü a Ul ÇoÁÆ rnoÁlUæÇo_çÇr b½r ~ p } lnpç} rõj p ö(p } u n l ~ p } ý ¿ r j æ p p £è pK} q ÿ o 'r p ¬ öp }¬ p ¬ £ÕpK}¬ ÔÈp }¬ ¬ lUÔÁrI£Ök anp ÿ o üÝÌb aSq¾ÿ}ýßéo }ê j r b lÿ}o ÿ}ñ}?r½£ j ¬ lÂ} ÿ o r ª ¬ lUÔÁr×£Ø p ¨ £ Ô~jlÿ o rQYp öRp~} } ª lÿ} o }ý r £éq ÿ o ' r ÿ } Ï>² Ï Ä ÿ p½ÓqlfÔqr ÿ}j p ÿ £ p }¸6 j ² ü{ a q¾ ÿ Ä o sr b anÿ o b h ÿ }¬ pÙÓûlfÔqr|£ lÿ o Qr £ ¬ lÿ o r ª lÿ o ½r £ q ÿ o sr ¯'° j aq¾ÿ o sr b ÿ lºm _o pÙ°sr h ÿ h }¬ ~ p r ôÙp ¼ö } ja ª ¬ l ª Ul ÔÁró ¬ ª l ª l f q Ô º r r S j ì b ~ p } Í ë Ô n ½ p ¼ ° o ÿ ·¹lº p~ »½} áh~j } Å{a ªupõlÂÿ } or¿ jÎ@r ¢ÀpöÀpõ}vÍ · lÂ·¹ÿ lóo$ »Á«r h~H} Åxp~p~} b} r¿jk·¼ÅäÆ r 'r ¸ p½ÓqlfÔqr £ ¹º aqÚûoóÿ ohqÚûo ® Á b ¸ jÛ± Ù p û Ó l f q Ô r ¨ £ ÔÏj lÂ ÿ o r pÙ² lDÃ oq¦ »ºÿ rðüp½²ólDÃ oq¦ » r r ÿ q ÿ o G ÿ o ¹º ²Ä ¬ q oG r Æ h } ¹ · n l h Ý r j kËÃË ¦ËÊ¿lfQ² r Æ j m ² ¹º ¬ lUÔn}ýrc£ Ñ ½fl Ôqr ¬ª fl Ôº}ñ r£ Ô Ôn}Qp½ÓqlfÔqr p ¬ £Üp ¬ üÝp½ÓqlfÔqr p~} p~m } hq ÿ oÑ } r j lnm _o pKh } ¬r m } ÿ Ns Þ h } ulnp } r¿j µAí¶î ï ·Dðhñ.ò ò ulÿ o r ß|j m ¬ öÀm ² ( Æ »Ò¼Ç»Òh~}¬ Sö p } lnp } r¿j µAí¶î ï ·Dðhñ òó ò lÿ o fr ´ Í ² Íèø ² Ym j agÏ ² b ßj a Ño à oÁ¦Ç}oÁ¦ } Â_o á b Ño ÏjBa ã ¦ o½¦ â }ýoq¦Ç@} Âä_o á bjva á½fo Ï b j ¦ o ja <o â b j o ÏsäQjå hõ} jlnm oÁp~} r h~} ùp ª p p ¬ h j lºm o_p r lnhõ·¼} ÅäÆÇr 5. h. 5. A minimum-cost arborescence of total cost 32 given by FSA+1. (see Fig. 2) is obtained Figure 7: A graph and a directed tree from at Step 9 of FSA+1 and an approximate so, where all self-loops are omitted, solid lution of Fig. 1 is ob( for any ) and arrows are edges in tained from at Step 10 of FSA+1, where dotted lines are edges in (bold dotted lines are . corresponding to edges in ). 5. 6.1.. . For each .. Figure 8:. ,. Set (i) if. , then , , , where ( or denotes or ) if or is in some or , respectively, or ( and ) otherwise; (ii) otherwise , , .. and. , execute 6.2. For each edge the following (1) and (2). (1) construct a set of directed edges by executing the following (a) or (b) (see Fig. 5).. (a) If one of , say , is an descendant of the other, , in , then (Fig. 5(1)). (b) Otherwise ( is not an descendant of and is not an descendant of in ), find a nearest common descendant of and , and execute either (b1) or (b2). (Note that (b2) is executed only if is even.) (b1) If then (Fig. 5(2)). (b2) If (that is, is a dummy vertex) then , where we assume that the -path and the -path of pass through and with , respectively (Fig. 5(3)).. . For each. and. 8. Find a minimum-cost arborescence rooted at in with respect to (see Fig. 8). 9. Construct a solution (with multiplicity deleted) such that . 10. Construct a solution (with multiplicity deleted) such that .. Remark 3.1 When we change a graph having multiple edges into a simple one, we choose an edge of minimum cost among those connecting and for any pair of vertices . Remark 3.2 If the problem is 2ECA-SV with and then FSA+1 is similar to the 2approximation algorithm of [14]. (2) and for each [Correctness of FSA+1] We show series of necessary , and then (see results, some of which are stated without proofs because of space limitation. Fig. 6). For a set or of edges, each connecting distinct 7. (1) Construct a maximal subgraph vertices of or of , respectively, let consisting of those edges on the -path of for any (see Fig. 7). (Note that is a reor verse arborescence rooted at .) (2) Let . Let ( ) denote the vertex set of any maximal tree in such that and . ( with , with , with The following lemma shows that it suffices to consider in Fig. 6.) Define , ECA-SV for a cactus (instead of and as follows. ) from the properties of a structural graph of . 5 −29−.

(9) vL. vR. U vip’(u) v p’(u)-1 i. Figure 9: A set. ô. u. p(u) vi p(u)+1 vi. of vertices in. h~}. h ¬ Þ ÿ @m1 } í h }¬ h~}¬ÅÎmÏpÙlÓû¯ lfø~rür ¥`jÎ ÿ>ý ÿ q ÿ oóÿ ý r Øp }¬ q ÿ ý oG r h }¬ ÿ ôÀkm ¬ 'ÿ ý^ ¸ ôkjÀa ÿþb >ÿ ýÈ j ± ®Á ¸ kËÊþ¹lÿ ` rô »Êþ }ñlÿ r ËÊ¿ôfl Qj?² r Â.² lDþ¹lÿ rºoÑþ } lÿ ÿÞrºr Þô B³² Þ ô ô µAí · ý B ÿ ô j ² µAí j ²ý ò · h~}¬ Å pÙþÓûfl fl ø~² rr ô fl ôsr 5ô ÿ fl ôsr >ÿ ý^ hõ}¬Ul ôsÅrp mvÓ lfl ø~¯ r r e Ul ôsr f l ¢ á ö ÆÇr s¸ r h~} 1m ö¸l ¸ fl ôsr÷ü fl ôsr ö ¸ Ul ¢èöxÆ r ÿ ý . ÿý ² ¸ hc ~} ÅÍfl ô ø rçö ¸ fl Ô¥¢Ñfl ôsjörlÆÇö Ár o ¸ r6Íø s YmÏl ¯ r ÏSSô h }¬ fl ôsr h }¬ iÅ p½Óqfl ø~r ö§m . cence . Suppose is the nearest vertex from in such that and is not reachable from in . Let denote the vertex with . Note that any inner vertex of path in is reachable from . We select the vertex set containing as in the following (a1) or (a2).. vi0. (a1) If. then. with as shown in Fig. 9, where is a maximal vertex set such that , and any vertex in is not reachable from . From the maximality of , and are reachable from in , where superindices of vertices in are mod .. (a2) If .. .. then. p }·¹h~lº} »Áh~} Åsln p põ} } r^r» ø u·¥lnp Å|p~} rÆ} ªulºpõ} r p~p j }} aª lÿ o rÍùlÿ o h~½r }=põ} bs ·¹lº»Áh~}ñÅõªulºpõ} rºrKø·p~Å¼}Æ Ñ lºp~} rKh~ø} ulfªulnp~} rºr ¹º h } ÿ ÿ hõ} ¹º h } ¹º h } l RGo y»½h~} r lÝDa Ïl }Ï } Go öUo Ð Ð¹}ñrn¸roûDl j Ï j!<o Dl ö 7r b } GoöEjæÑß }ÂDl »½Rh~o } ¥r »Áh~} r }¿ö l¸ } oGÏ÷j }ñ»½h~ } ö r ß } ö ¸ j ö ß Ï} ö ¸ Dl R!j o ¥»ÁEö h~}ß r ¸ öõ£Ò a l Ï Uo lDÐ¹RrnoûoDl ¸Ï <o »½ö h~r }bèr jiª ¬ Dl TGo yª »½h~} r ¹º S ¸ Îj ÿ>ý ö|£&ÿ} r } ÿ qÚÏ Ño Ð ÿ Bÿ h }¬ èj{ÿ'ý@ ¸ ö p ¬ ö5p }¬ h ¬ DÏ}ýoGÐ }ñrj ª ¬ lgqÚÏ oÑÐ r re7p l ÐÇRga Ï}ýGo Ð } b r ¹º Kj± ® Á ²Ä RmslfQ² r q ½o r Ú q Ï o Ñ Ð ÿ p öÍpK} h qÚÏ} oGÐ } r j ª lfqÚÏ oÑÐ r rÝ§p ¬ h }¬ þ }Âlÿ r×Ë(ÃËEöþ£ lf ² r kË|ÃÝË|þ¹lÿ r õ ö £ Ï Ð Ï} Ð } h }¬ ¹º Ô ½p 5ö7p~} pÙÓ fl ÔqrBj a Ôn! } êp Í ö öÇ ¸ ö^ lfôsr ª lfÔº} r p½ÓqlfÔqrub pÙÓqlUø~rðj ù ðhú p½ÓqlfÔqr ö p½ÓqlfÔqr p½Ó fl ø~rÝj ù ð<ú p½Ó Ul ÔÁr sr |p½ÓqlfÔqrsnp½Óqlfø~r Ñ q ö o lfôsr qÑö o 'r h }¬õÅip½Óqlfø~r m h } Åi·¹pÙlºÓ lf ø~»½h~r } ÎÅ ø~rÑØø ø ¢ p ¹º ø p ·¹ló »½h~} Åcøõrø¢ ø p h } ÅpÙÓ lfø~r p ÿShR} m ÅÊp½Ó lfø~r h } ÿ oÑs »½h~} i ¹ · ó l Å øõrû ø ¢ ø\ôp h~}¬¿Åp½Óqlfø~r s sm ¬ h c Å Ù p q Ó U l ~ ø r ¬ } h }¬ Å pÙÓûfl ø~r ·¹lº »Áh~} Å ø~=rðm Îø ¬ ¢ ÿ ¹º h }¬ ¯ ï ·¹lº »Áh~} Åp~} rÏøØ¢ põ} Lemma 3.1 If then there is is a solution to. for some such that . For a set , let with multiplicity deleted. If is a solution to and then and . Clearly, satisfies the following Properties 3.1, 3.2 and 3.3 from its construction. Property 3.1 If is an descendant of in , is reachable from in . Property 3.2 Any pair of dummy vertices in are not adjacent in . Property 3.3 If is any minimum -cut which is either a bridge or a 2-cut such that then there is a -bridge with and . Conversely if is any -bridge then there is a minimum -cut such that and , and is either a bridge or a 2-cut such that . Backpointers and , respectively, have the following Properties 3.4 and 3.5 from its construction. Property 3.4 If there is any directed edge in and then . Property 3.5 If there is any directed edge in and then ( , respectively) is a descendant of ( ) in . For , let is included in . Let and . Lemma 3.2 (Lemma 3.3, respectively) shows strongly connectedness of in ( in ), where is any set of edges such that . As an example of such , see (bold dotted lines) in Fig. 2 and the edges (bold dotted lines in Fig. 7) corresponding to . Lemma 3.2 If for a set then is strongly connected in . Proof : Suppose that is not strongly connected in , while holds. Clearly, is reachable from any vertex through edges in . Let denote the subtree induced by the set of all ancestors (including itself) of in the reverse arboreswith and. Let denote the union of over all . Clearly , , and any vertex in is not reachable from in . There is a -cut in separating from . Let be such any -cut. If then is a bridge or a 2-cut consisting of multiple edges; if then is a 2-cut consisting of two edges in . Because is not a -cut separating in , there is an edge such that and . Suppose that . Let be the nearest for some vertex common descendant of and in , where may be equal to . Then and is reachable from in . We select a vertex as in the following (b1) or (b2).. (b1) The case with. . Then. (Fig. 10).. (b2) The case with . If then (Fig. 11), where is the parent of on the path then we set to from to in . If either or by the following rule (Fig. 12). Let and be the vertex in the path in . Then set if , or if .. For such a vertex , we have and , and is reachable from . From the construction of , there is an edge . This means that is reachable from by using ,a contradiction. Lemma 3.3 If for a set then is strongly connected. Proof : Let be any leaf in . Clearly holds. Then is strongly connected because, from Lemma 3.2, is strongly connected in , that is, there is a directed cycle containing both of and . Lemma 3.4 FSA+1.. 6 −30−. for. in Step 9 of.

(10) r t. up u U. D(U). j lnm o r Ï o l rár ö l $ v r ö á ý } o } j l Ï o l á} ño } rÑj l è}ýo } r } } h} { } j } m qlól ál } áýo } ýo}ñrºr }Âr Tp~} á} l r } l l r övÆÇr h~} Å{põ}. ¯ ° ' r <p ° in Step 8 of FSA+1. ¯° Ú q ± Ø p U w | such that ± ° fw ß . Let q/± r ª gqÚ± sr andß ª ¬ gqÚ± r . From Properties 3.4 and 3.5, D± (± , respectively) is a descendant of (± ) in ¬ , Î . Then, by the construction of and pÙÓ D± , we have ± % fw and ü fw . Be cause D± Ù , this contradicts that is a f¢ cut separating in ¹º . borescence has an edge and. s. x. v. The next lemma shows the performance ratio of FSA+1. in the proof of Lemma Lemma 3.5 Let be an approximate solution for 3.2 ECA-SV by FSA+1 and be an optimum solution for ECA-SV. Then . r Proof : Let denote the set of edges of corret sponding to of . By Lemma 3.1, is an opu’ timum solution such that . We will show that . From Lemma 3.3, up is strongly connected and, therefore, it s u x contains an arborescence rooted at . U Since is a minimum-cost arborescence in , we have . is an arborescence, contains at most Because D(U) v two edges of for each . All edges of have the same cost . Hence Figure 11: The case with and in the proof . Moreover, holds, meanof Lemma 3.2 ing that . Because , we get . - -cut exists in . Proof : Suppose a Remark 3.3 Although Step 6 of FSA+1 keeps all edge Then is a - -cut of and is a bridge or a of , keeping only one minimum-cost edge for each 2-cut. Let be defined from by the following. ordered pair with (see (i) or (ii). pairs , , in Fig. 6) is sufficient for us (i) If is a bridge in then , where to find a minimum-cost arborescence. Our algorithm can be easily modified so that Step 8 may be done in and . time if is even. Even with this imincluded in the same cycle provement, however, overall time complexity of FSA+1 (ii) If is a 2-cut in of then , where we assume is still if is even. that , with Theorem 3.1 FSA+1 is a 2-approximate algorithm for , and their superindices are mod ECA-SV with . Its time . complexity (space complexity, respectively) is ( ) if is even, or Let be the union of over all vertices ( ) if is odd. in . Clearly holds. From Lem- Proof : The correctness is proved by Lemma 3.4. By mas 3.2 and 3.3, ( ) is strongly Lemma 3.5, is shown. We are going to show connected. Therefore we can find a minimum-cost ar- that FSA+1 takes time if is even, and if is odd. Constructing , and can be r done in time, where is time complexity of obtaining a structural graph of at Step 1 of FSA+1 t=u p and . Step j 2 takes time. Because has vertices vi and edges, Steps 3, 4, 5 and 6.1 take time. In u x vR vL Step 6.2, it is necessary to find nearest coms U mon descendants for each edge in . It is can be done in time by using an algorithm by [11]. D(U) v In Step 6.2 (a), only one edge is produced. In Step 6.2 (b1), two edges are produced, while, in Step 6.2 Figure 12: The case with and in the proof (b2), edges may be produced. So, Step 6.2 of Lemma 3.2 takes time, where if is odd then Step 6.2. ln·áÅRÆÇr ln·sÅHÆÇr p~} plnp~ } r½»Î ulnp r u pp h~} ·¹lº »Áhõ} Å p pr@ øh~} ¢ h } iÅ pÙÓ lnp r lnp~} r6»Ò¯ Y lnj p lnr m o_pX nr ¯'° h fl p½°v¯½r » fl p r ¯ pÙÓ fl Ôqr ÔÎ p fl p« ur5» Ù p Ó l f q Ô r U û l f q Ô r ¸ j@ ÿ>ý Uqlnpõ r Ñ½lnp~} r^» lfp ° r Ñ qlnp~} ½r »c Ñ qln p »È r lnp r¿Îj ulnÇp~uln} ýp rK ujÀr Ñ ½lnp~} ¹ºr. u n l ~ p } ý ¿ r j n l ~ p } r Q . lwxf¢smöi lfÆÇ¢ðr ö9s ÆÇr ' h~} hõ} Åäp~} p ¬ e a ÿ o b æm ¬ m ¬ q ÿ o sr ip ¬ aoG¼ûb ag o<¾ b ag¿oUàb. h~} Ô ! w £ a ÿ b Ô jlÿ o ÿ r½Rp~¬} q ÿ oóÿ r ëpK}¬ ËvlnÍÎmÏÍ o r ·¹lº»Áh~}r. Ô o_Ô o b a Q² h~} Ä w| £ÕÂ0²ólDÃ oq¦ r ËslºÌiÅxÍÎmÏÍÐÍÎpÑÍÒr ·¹ló$»Áh~}Âr ¹º Ô j l ² o ²Ä r Ô o j l ²Æ o ²Æ r kË Ã» ¦ÈË÷¿lUQ² r ln·ÅkÆÇr ·@jF·¹lnhç}ñr j·¹lº»Áh~}r ËvlóÌBÅ ¿lfQ² r ÍÎmÏËsÍÐl ÍÎÍÎpÑmÏÍÒÍÁr ÅxËsÍÎpÏl ÍÎÍÒmÏr Í o¼Å|· ÍÒpÑÍòr · ËslºÌïÅæÍÎpÏÍÒr fw$ráÀm ¬ l s m D¯ r l @Sw hõ}¬ ·¹lº »ÁÅ h p½rçÓ Îø lnp ¢ öRp~} r h j h } õ ì j Ëslº ÌkÅiÍÎmÏÍÐÍÒpÍòr · ËvlóÌyÅÝÍÎpÏËsÍÒlºr ÌÀÅ· ÍÒpÑÍòr Ìh~} h~} ª Ì cj Ësx@l ÍÒpÏz}{¹ÍÒaÇr ÍÎmÑÍÎ pá}ÂÍÒo ÍÎpõ}ýÍ ÅäB· h~o ÍÎ} mÏÍ , ËvlnÍÎlnmÝÍÎmÏ:Í ÇÍÒ·¹r r b Ësl ÍÒpÙpÏËs ÍÒr l ÍÒmÏÍÒr Ësl ÍÎpÏÍòr. ¸ Figure 10: The case with . ¸. çj@ÿ>ý. sËËvllnÍÎÍÎmÏmÏÍÎÍÒr pÑÍÒr. . 7 −31−. ·.

(11) Ësl ÍÒpÏËsÍÒl r ÍÎmÏÍÎ pÑÍÒr vË lnÍÎpÏÍÒr Ësl ÍÎmÏÍ÷¯>Å|° ÍÒpÑÍòr · ËsDl "\Å @,0þr " Ësl ÍÎmÏÍ oáÅ|ÍÒpÑÍòr Ësl ÍÎpÏËsÍòl r ÍÒmvÍ}h K¬ ÍÒmÑÍ ÅHÍÎmÏÍ o~hÅ{¬ ÍÒpÑÍò· r Ëvl ÍÒmÏÍ,KÍÎmÏÍ Å¸ÍÒpÑÍòr Ësl ÍÎmÏÍòr. (b2) is not executed and time is to be spent in Step 6.2. Step 6.2 takes ( , respectively) time if is even (odd). Step 7 is done in time. Finding a minimum-cost arborescence in Step 8 takes time by using the algorithm of [7], where ( , respectively) is the number of edges (vertices) in . Because has edges ( edges, respectively) if is even (odd), Step 8 takes time ( ). Steps 9 and 10 take time. Thus the time complexity as stated follows. Explanation of space complexity is omitted.. ¹º. lº·þÅ¥ÆÇr ËslºÌTÅ ÍÎpÏÍÒr rXxp öip~} l ÿ o h }¬ aÿ o b ÿ ¹º ~ p } lº· ÅÝÆÇr ¹ · º l Á » õ h ý } r À j ¹ · n l ç h ñ } ¿ r À j · ËslºÌkÅiÍÎpÏÍÒpõr } ulnp } rX»§ulnp r p } p p r ¯ p½Óqln ¬ fl p½Óqlnp rºrHÔxjjÑ llºÿ p o rr(ôp ¯ q¾ÿ o 'r a ª fl q ÿ o sr r bïj p½Óqfl Ôqr ulnp~} r jÀ fllnpõp~l} ¯rÙ q» rºÌr » lfp½ °Ï¬ fl r½p½» Óqlnp lfrºpõryl¯j rºÑ r½qlº»p u lnr p r. 4. An optimally solvable case. We can prove that ECA-SV is solvable in time if the following condition holds (meaning that Step 6.2 (b) of FSA+1 is not executed). Condition 4.1 For any edge , one of , say , is an descendant of the other, , in in Step 6.2 of FSA+1. Theorem 4.1 If Condition 4.1 holds then given by ECA-SV for the FSA+1 is an optimum solution to case with , and its time complexity is . Proof : Clearly is a solution to the problem. So it is enough to show . We consider , and in Lemma 3.5. By the construction of , we have when Condition 4.1 holds. Because, for , contains exactly one edge with , we have . Thus .. ¹º. [11] [12]. [13]. [14]. [15]. [16]. [17]. [18]. [19]. [20]. [21]. [22]. [23]. References [1] K. Eswaran and R. Tarjan, “Augmentation problems,” SIAM J. Comput., Vol. 5, pp. 653–655, 1976. [2] S. Even, Graph Algorithms, Pitman, London, 1979. [3] A. Frank, “Augmenting graphs to meet edge connectivity requirements,” SIAM J. Discrete Mathematics, Vol. 5, No. 1, pp. 25–53, 1992. [4] G. N. Fredericson and J. Ja’ja’, “Approximation algorithms for several graph augmentation problems,” SIAM J. Comput., Vol. 10, pp. 270–283, 1981. [5] H. Gabow, “Applications of a poset representation to edge connectivity and graph rigidity,” in Proc. 32nd IEEE Symposium on Foundations of Computer Science, pp. 812–821, 1991. [6] H. Gabow, “Efficient splitting off algorithms for graphs,” in Proc. 26th ACM Symposium on Theory of Computing, pp. 696– 705, 1994. [7] H. Gabow, Z. Galil, T. Spencer, and R. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica, Vol. 6, No. 2, pp. 109–122, 1986. [8] H. Gabow, M. Goemans, and D. Williamson, “An efficient approximation algorithm for the survivable network design problem,” Mathematical Programming, Vol. 82, pp. 13–40, 1998. [9] M. R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. [10] M. X. Goemans, A. V. Goldberg, S. Plotkin, D. B. Shmoys, ´ Tardos, and D. P. Williamson, “Improved approximation alE. gorithms for network design problems,” in Proceedings of the. [24]. [25]. [26]. [27]. [28]. [29]. [30]. 8 −32−. fifth annual ACM-SIAM symposium on Discrete algorithms. pp. 223–232, ACM Press, 1994. D. Harel and R. Tarjan, “Fast algorithm for finding nearest common ancestors,” SIAM J. Comput., Vol. 13, pp. 338–355, 1984. K. Jain, “A factor 2 approximation algorithm for the generalized Steiner network problem,” Combinatorica, Vol. 21, pp. 39–60, 2001. A. V. Karzanov and E. A. Timofeev, “Efficient algorithm for finding all minimal edge cuts of a nonoriented graph,” Cybernetics, pp. 156–162, March-April 1986, Translated from Kibernetika, 2 (1986), 8–12. S. Khuller and R. Thurimella, “Approximation algorithms for graph augmentation,” Journal of Algorithms, Vol. 14, pp. 214– 225, 1993. S. Khuller and U. Vishkin, “Biconnectivity approximations and graph carvings,” Journal of the ACM, Vol. 41, No. 2, pp. 214– 235, 1994. T. Mashima and T. Watanabe, “Approximation Algorithms for the

(12) -Edge-Connectivity Augmentation Problem,” in 1995 IEEE International Symposium on Circuits and Systems, pp. 155–158, May 1995. H. S. Nakamura, and T. Ibaraki, “A simplified Nagamochi, time edge-splitting algorithm in undirected graphs,” Algorithmica, Vol. 26, pp. 50–57, 2000. D. Naor, D. Gusfield, and C. Martel, “A fast algorithm for optimally increasing the edge connectivity,” SIAM J. Comput., Vol. 26, No. 4, pp. 1139–1165, Aug. 1997. S. Taoka and T. Watanabe, “Minimum augmentation to

(13) -edgeconnect specified vertices of a graph,” in Lecture Notes in Computer Science 834(D-Z du and X-S Zhang(Eds.): Algorithms and Computation), pp. 217–225. Springer-Verlag, Berlin, 1994, (Proc. 5th International Symposium on Algorithms and Computation(ISAAC’94)). S. Taoka and T. Watanabe, “Efficient augmentation to edge-connectspecified vertices of a graph,” preparing to publish, 2002. R. Tarjan, Data Structures and Network Algorithms, CBMSNSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1983. S. Ueno, Y. Kajitani, and H. Wada, “Minimum augmentation of trees to

(14) -edge-connected graph,” Networks, Vol. 18, pp. 19–25, 1988. T. Watanabe, Y. Higashi, and A. Nakamura, “Construction robust networks by means of graph augmentation problems,” Trans. IEICE of Japan, Vol. 73-A, No. 7, pp. 1242–1254, 1990, (in Japanese) Also see Electronics and Communications in Japan, Part 3, Vol. 74, No. 2 (1991), 79–96. T. Watanabe, T. Mashima, and S. Taoka, “The

(15) -edgeconnectivity augmentation problem of weighted graphs,” in Lecture Notes in Computer Science 650, Algorithms and Computation, T. I. , Y. Inagaki, K. Iwama, T. Nishizeki, and M. Yamashita, Eds. Springer-Verlag, Berlin, 1992, (Proc.3rd International Syposium on Algorithms and Computation(ISAAC’92)). T. Watanabe, T. Mashima, and S. Taoka, “Approximation algorithms for minimum-cost augmentation to

(16) -edge-connect a multigraph,” in Proc. 1993 IEEE International Symposium on Circuits and systems, pp. 2556–2559, May 1993. T. Watanabe and A. Nakamura, “Edge-connectivity augmentation problems,” Journal of Computer and System Sciences, Vol. 35, No. 1, pp. 96–144, 1987. T. Watanabe, T. Narita, and A. Nakamura, “3-edge-connectivity augmentation problems,” in Proc. 1989 IEEE International Symposium on Circuits and Systems, pp. 335–338, 1989. T. Watanabe, S. Taoka, and T. Mashima, “Approximation algorithms for the 3-edge-connectivity augmentation problem of graphs,” in Proc. IEEE Asia-Pacific Conference on Circuits and Systems, pp. 424–429, Dec. 1992. T. Watanabe, S. Taoka, and T. Mashima, “Minimum-cost augmentation to 3-edge-connect all specified vertices in a graph,” in Proc. 1993 IEEE International Symposium on Circuits and Systems, pp. 2311–2314, May 1993. T. Watanabe and M. Yamakado, “A linear time algorithm for smallest augmentation to 3-edge-connect a graph,” IEICE Trans. Fundamentals, Vol. E76-A, No. 4, pp. 518–531, 1993..

(17)

&lambda;-辺連結グラフにおける指定点集合の（&lambda;+1）-辺連結化のための2-近似アルゴリズムFSA+1

λ-辺連結グラフにおける指定点集合の（λ+1）-辺連結化のための2-近似アルゴリズムFSA+1