| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-06-29 09:50 有向グラフにおけるk枝連結性の検査 ○吉田悠一・伊藤大雄（京大）  COMP2007-20 |
|
| 抄録 | （和） | 本報告では、次数に上限のある有向グラフが$k$枝連結であるか、または$k$枝連結から$\epsilon$遠隔であるかを検査する、グラフの頂点と枝の数によらない定数時間アルゴリズムを示す。 頂点数$n$、次数の上限$d$の有向グラフ$G$が$k$枝連結から$\epsilon$遠隔であるとは、次数の上限を保ったまま$G$を$k$枝連結にするのに、少なくとも$\epsilon dn$本の辺の追加及び削除が必要であることを言う。 本報告で示す検査アルゴリズムは、性質検査（Property Testing）と呼ばれる概念に基づいている。 これは入力グラフが$k$枝連結であれば$2/3$以上の確率で受理し、$k$枝連結から$\epsilon$遠隔であれば$2/3$以上の確率で拒否するものとして定義される。 どちらでもないグラフに対しては、何を出力してもかまわない。 我々は、$k$-1枝連結なグラフに対して$O\left(d\left(\frac{c}{\epsilond}\right)^{k}\log\frac{1}{\epsilon d}\right)$$($$c>1$は定数$)$時間、一般のグラフに対して$O\left(d\left(\frac{ck}{\epsilon d}\right)^{k}\log\frac{k}{\epsilon d}\right)$$($$c>1$は定数$)$時間の検査アルゴリズムを得た。 |
| （英） | In this paper, we show constant time algorithm for testing whether a given degree-bounded digraph is $k$-edge-connected or $\epsilon$-far from k$-edge-connected. A digraph of $n$ vertices with degree bound $d$ is $\epsilon$-far from $k$-edge-connected, if at least $\epsilon dn$ edges have to be added or deleted to make the graph $k$-edge-connected, preserving the degree bound. Our algorithm is a testing algorithm in the sense of ``Property Testing''. Property testing is defined as follows: If the input graph is $k$-edge-connected, it must output ``Accept'' with probability at least $2/3$, and if the input graph is $\epsilon$-far from $k$-edge-connected, it must output ``Reject'' with probability at least $2/3$. It can output any for a graph which is neither $k$-edge-connected nor $\epsilon$-far from $k$-edge-connected. Since testing can be regarded as reduction of decision, the complexity of testing algorithms is expected to be smaller than that of decision algorithms. This paper presents an $O\left(d\left(\frac{c}{\epsilon d}\right)^{k}\log\frac{1}{\epsilon d}\right)$$($$c>1$ is a constant$)$ time algorithm for ($k$-1)-edge connected graphs and an $O\left(d\left(\frac{ck}{\epsilon d}\right)^{k}\log\frac{k}{\epsilon d}\right)$$($$c>1$ is a constant$)$ time algorithm for general graphs. |
|
| キーワード | （和） | グラフ理論 / 性質検査 / 有向グラフ / $k$枝連結性 / / / / |
| （英） | graph theory / property testring / digraph / $k$-edge-connectivity / / / / | |
| 文献情報 | 信学技報, vol. 107, no. 127, COMP2007-20, pp. 17-23, 2007年6月. | |
| 資料番号 | COMP2007-20 | |
| 発行日 | 2007-06-22 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2007-20 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2007-06-29 - 2007-06-29 |
| 開催地（和） | 北海道大学 |
| 開催地（英） | Hokkaido University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2007-06-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 有向グラフにおけるk枝連結性の検査 |
| サブタイトル（和） | |
| タイトル（英） | Testing k-Edge-Connectivity of Digraphs |
| サブタイトル（英） | |
| キーワード(1)（和/英） | グラフ理論 / graph theory |
| キーワード(2)（和/英） | 性質検査 / property testring |
| キーワード(3)（和/英） | 有向グラフ / digraph |
| キーワード(4)（和/英） | $k$枝連結性 / $k$-edge-connectivity |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 吉田 悠一 / Yuichi Yoshida / ヨシダ ユウイチ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 伊藤 大雄 / Hiro Ito / |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-06-29 09:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2007-20 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.127 |
| ページ範囲 | pp.17-23 |
| ページ数 | 7 |
| 発行日 | 2007-06-22 (COMP) |
[研究会発表申込システムのトップページに戻る]