2024-03-29T07:26:42Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000809692023-04-27T10:00:04Z01164:02592:06670:06707
リーフの最近分岐点を用いたグラフの2辺連結化アルゴリズムAlgorithms to 2-Edge-Connect a Graph by Using Nearest Branch-Vertices of Leavesjpnショートトークhttp://id.nii.ac.jp/1001/00080969/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=80969&item_no=1&attribute_id=1&file_no=1Copyright (c) 2012 by the Information Processing Society of Japan広島国際大学広島大学広島大学間島, 利也田岡, 智志渡邉, 敏正グラフの 2 辺連結化問題とは,無向グラフ G = (V,E) が与えられたときに,G に辺集合Fを付加することにより得られるグラフが 2 辺連結となるような,辺数最小の付加すべき辺集合 F を求める問題である.本稿では,グラフの 2 辺連結化問題を解く線形時間アルゴリズムとして,リーフの最近分岐点を用いたアルゴリズムを示す.The 2-edge-connectivity augmentation problem of a graph, 2ECA, is defined as follows: ”Given an undirected graph G = (V,E), find a smallest set F of edges such that (V,E ∪ F) is 2-edge-connected.” In this paper, we show two linear time algorithms for solving 2ECA. Each of the two algorithms is based on the method for searching nearest branch-vertices of leaves in a tree, where a branch-vertex of a tree is a vertex of degree at least three.AN1009593X研究報告アルゴリズム(AL)2012-AL-1392162012-03-072012-03-07