講演名 | 2011-12-16 木,カクタスにおける点被覆の遷移可能性 野岡 弘幸, 伊藤 健洋, 周 暁, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 本文では,グラフGの点被覆が2つ与えられたとき,その一方から他方へGの点被覆のみを経由して,段階的に遷移する事ができるか判定する問題を扱う.ただし,遷移の過程に現れるGの点被覆は,そのサイズが与えられた整数k以下でなければならなく,一つ前の点被覆からちょうど1点を付け加えるか取り除くことで得られなければならない.この判定問題は,平面グラフに対してPSPACE完全である事が知られている.本文では,グラフをカクタスに制限したとき,どの点被覆の組でも常に遷移できるためのkに関する十分条件を与える.また,木に対しては,与えられた2つの点被覆が遷移できるための最小のkを計算する線形時間アルゴリズムを与える. |
抄録(英) | We study the problem of reconfiguring a vertex cover of a graph G into another vertex cover via vertex covers of G, each of which results from the previous one by deleting or adding a single vertex, without ever going through a vertex cover of size more than k, for a given integer threshold k. This decision problem is known to be PSPACE-complete for planar graphs. In this paper, we first give a sufficient condition on the threshold k for which there always exists a reconfiguration between any two vertex covers for cacti. We then give a linear-time algorithm for trees to compute the minimum threshold k for which there exists a reconfiguration between two given vertex covers. |
キーワード(和) | アルゴリズム / 解空間の到達可能性 / カクタス / 木 / 点被覆 |
キーワード(英) | algorithm / cactus / reachability on solution space / tree / vertex cover |
資料番号 | COMP2011-39 |
発行日 |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 2011/12/9(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Theoretical Foundations of Computing (COMP) |
---|---|
本文の言語 | JPN |
タイトル(和) | 木,カクタスにおける点被覆の遷移可能性 |
サブタイトル(和) | |
タイトル(英) | Reconfiguration of Vertex Covers in Trees and Cacti |
サブタイトル(和) | |
キーワード(1)(和/英) | アルゴリズム / algorithm |
キーワード(2)(和/英) | 解空間の到達可能性 / cactus |
キーワード(3)(和/英) | カクタス / reachability on solution space |
キーワード(4)(和/英) | 木 / tree |
キーワード(5)(和/英) | 点被覆 / vertex cover |
第 1 著者 氏名(和/英) | 野岡 弘幸 / Hiroyuki NOOKA |
第 1 著者 所属(和/英) | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
第 2 著者 氏名(和/英) | 伊藤 健洋 / Takehiro ITO |
第 2 著者 所属(和/英) | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
第 3 著者 氏名(和/英) | 周 暁 / Xiao ZHOU |
第 3 著者 所属(和/英) | 東北大学大学院情報科学研究科 Graduate School of Information Sciences, Tohoku University |
発表年月日 | 2011-12-16 |
資料番号 | COMP2011-39 |
巻番号(vol) | vol.111 |
号番号(no) | 360 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |