| 講演名 | 1994/4/27 平面グラフ上の極大f-依存点集合問題がNCに入る 陳 致中, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 極大f-依存点集合問題は、グラフG=(V,E)と関数f:V→Nが与えられたとき、次を満たす極大なU⊆Vを求める問題である:Uによって導出されるGの部分グラフにおいてどの頂点uの次数もf(u)を越えない。この問題がNC(またはRNC)に入るかどうかは未解決である。Diksらは、fの値が入力グラフGのサイズの対数多項式で抑えられれば極大f-依存点集合問題がNCに入ることを示した。本研究では、入力グラフGが平面グラフであれば、極大f-依存点集合問題がNCに入ることを証明する。 |
| 抄録(英) | The maximal f-dependent set(Max-f-DS)problem is the following problem:Given a graph G =(V,E)and a nonnegative integer-valued function f defined on V,find a maximal subset U of V such that no vertex u ∈ U has degree>f(u)in the subgraph induced by U.Whether t he problem is in NC(or RNC)or not is an open question.Concerning this question,only a rather trivial result due to Diks,Garrido,and Lingas is known up to now,which says that the problem can be solved in NC if the maximum value of f is poly-logarithmic in the input size£Proceedings of the 2nd International Symposium on Algor ithms,LNCS 557(1991)385-395!.In this paper,we show a nontrivial interesting result that the Max-f-DS problem for planar graphs can be solved in O(log^5n)time with 0(n)processors on a CRCW PRAM, where n is the input size. |
| キーワード(和) | 並列アルゴリズム / 極大化問題 / 計算量の理論 / グラフの理論 |
| キーワード(英) | Parallel algorithm / maximality problem / computational complexity / graph theory |
| 資料番号 | COMP94-1 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1994/4/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 平面グラフ上の極大f-依存点集合問題がNCに入る |
| サブタイトル（和） | |
| タイトル（英） | The Maximal f-Dependent Set Problem for Planar Graphs Is in NC |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 並列アルゴリズム / Parallel algorithm |
| キーワード(2)（和/英） | 極大化問題 / maximality problem |
| キーワード(3)（和/英） | 計算量の理論 / computational complexity |
| キーワード(4)（和/英） | グラフの理論 / graph theory |
| 第 1 著者 氏名（和/英） | 陳 致中 / Zhi-zhong Chen |
| 第 1 著者 所属（和/英） | 東京電機大学理工学部数理学科 Department of Mathematical Sciences,Faculty of Science and Engineering,Tokyo Denki University |
| 発表年月日 | 1994/4/27 |
| 資料番号 | COMP94-1 |
| 巻番号（vol） | vol.94 |
| 号番号（no） | 26 |
| ページ範囲 | pp.- |
| ページ数 | 9 |
| 発行日 | |