著者

小池 敦 定兼 邦彦

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2016-AL-159, no.7, pp.1-8, 2016-09-16

---

本論文では,道路ネットワーク上の経路探索クエリについて,新しいアルゴリズムを提案する.提案手法は Hub Labeling や Pruned Highway Labeling と同様,ラベリング法に基づくものである.前処理において,入力グラフを複数の木に分解し,各ノードが hub ノード集合の代わりに木の ID の集合を保持することでラベルサイズを削減させる.本論文ではアルゴリズムを実装し,米国の道路ネットワークを用いて評価を行うことで,提案アルゴリズムの有効性を示す.

著者

御船 雄太 宮北 和之 中野 敬介

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2014, no.13, pp.1-6, 2014-11-13

---

比較的長い通信遅延を許容して情報伝送を行うためのネットワークを遅延耐性ネットワーク (Delay Tolerant Network: DTN) と呼ぶ.本報告では,無線端末同士の情報交換および移動により情報拡散を行うエピデミック伝送により実現される DTN を考える.エピデミック伝送の用途としてはある特定の端末に対する情報配信の他に,地域情報配信や災害時情報配信のように,ある特定の空間にいる不特定の端末への情報伝達も考えられる,このとき,特定の場所や空間に情報を "滞留" させておく必要があり,エピデミック伝送を用いた情報滞留が検討されている.本報告では,エピデミック伝送による情報滞留の応用として,商店街においてクーポンを情報滞留させ,景品の引換所に客を誘導することにより商店街全体で客を誘導することを考える.ここでは,情報の過度な拡散を防ぐために,端末の情報の送信を空間的に拡散制御しながら実現する情報滞留を考え,情報の魅力度,および景品の交換所の数や設置場所が客の誘導に与える影響について計算機シミュレーションにより評価する.A network that enables us to exchange information by tolerating a long delay time is called a Delay Tolerant Network (DTN). In this report, we consider DTNs realized by epidemic transmissions, in which information is spread by wireless transmission between nodes and mobility of the nodes. A DTN can be used to transmit information to unspecified nodes in a specific area. Such situations can be seen in information delivery in a local area and that in disaster situations. For this purpose, information has to be floated in the destination space so that nodes entering the space later get the information as well as nodes being there. In this report, we consider to steer nodes toward a shopping area by floating electric coupons that can be exchanged into a gift at exchange places in the shopping area. We consider to realize information floating by epidemic transmissions with spatial transmission control for suppressing useless information spreading, and evaluate the effects of attractiveness of information, the number and locations of exchange places on the effectiveness of steering the nodes by computer simulation.

著者

中原 孝信 宇野 毅明 羽室 行信

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2013, no.27, pp.1-8, 2013-10-30

---

本研究は,Twitter の投稿内容に,データ研磨技術を用いたマイクロクラスタリングを利用することで,単語の共起関係に基づいたクラスタによる概念を構築する.そして興味対象となるツイートをできる限り多く被覆するような少数のクラスタを,ナップサック制約付き最大被覆問題を用いて抽出することで,投稿内容の要約を行う.抽出されたクラスタは,ある特定のツイート群の文章を特徴付ける単語のグループとして捉えることができ,それらを概念として扱う事で,単語を独立に扱った場合に比べて,すぐれた要約になっていることを示す.計算実験では,テレビアニメーション番組「宇宙兄弟」に関する投稿内容を対象にして提案手法を適用した.This research proposes a method to detect the contents of Twitter posts by analyzing the contents of tweets posted by viewers watching a specific TV program whenever the number of posts increase dramatically and then to summarize that content. First the proposed method creates concepts from clusters based on the co-occurrence of words. Then posts during tweet bursts are taken to be tweets of interest, and a minimal number of clusters that cover as much as possible those tweets are extracted using a knapsack-constrained maximum covering problem. A computational experiment shows the effectiveness of the proposed method with reference to a TV animation program "Space Brothers."

著者

Tadachika Oki Satoshi Taoka Toshimasa Watanabe

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-131, no.10, pp.1-8, 2010-09-15

---

The k-edge-connectivity augmentation problem with multipartition constraints (kECAM for short) is defined by “Given an undirected graph G = (V, E) and a multipartition π = {V1, . . . , Vr} of V with Vi ∩ Vj = ∅ for ∀i, j ∈ {1, . . . , r} (i ≠ j), find an edge set E' of minimum cardinality, consisting of edges that connect distinct members of π, such that G' = (V, E ∪ E') is k-edge-connected.”In this paper, we propose a fast algorithm for finding a solution to (σ+1)ECAM when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}. The main idea is to reduce (σ + 1)ECAM to the bipartition case, that is, (σ+1)ECAM with r = 2. Moreover, we propose a parallel algorithm for finding a solution to (σ + 1)ECAM, when a structural graph F(G) which represents all minimum cuts of G is given and σ is odd.

著者

奥山 拓哉 吉村 地尋 林 真人 田中 咲 山岡 雅直

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2016-AL-158, no.14, pp.1-7, 2016-06-17

---

組合せ最適化問題を省電力かつ高速に解くため,イジングモデルの基底状態探索問題に変換して回路動作で解探索するイジング計算機が提案されている.半導体回路で空間的に効率良く表現可能なイジングモデルは規則的な構造であり,任意の最適化問題を解くためには基底状態を保持しつつモデルを変換する必要がある.本報告では Contractive graph minor-embedding を提案する.提案手法により対角線付き格子グラフに対してスピン数 100 のイジングモデルを 1 秒以内に変換する見込みを得た.

著者

Amanj Khorramian Tomoko Taniguchi Takeaki Uno Ryuhei Uehara

雑誌

研究報告アルゴリズム(AL) (ISSN:21888566)

巻号頁・発行日

vol.2018-AL-168, no.2, pp.1-8, 2018-05-18

---

Othello, also known as Reversi, is a quite well known strategy board game for two players on a board of size 8 ×8. The set of all reachable patterns is not yet known for this game. In this paper, we finally obtain all reachable patterns on 5 × 6 board by developing nontrivial algorithm on a supercomputer. We observe the scale of complete search-tree is big even for a board of size 5 × 6 and parallelize a distributed frontier search using shared memory to reach the final depth of the tree. To reduce the memory requirement, the tree is horizontally compressed using a novel method, and the frontiers are maintained in a novel data-structure. Moreover, an efficient number system is proposed and utilized for representing the states of the game, and a symmetry of the states is applied during the search. We assume that the board and pattern are rotation symmetry, but we assume that the mirror symmetry gives the different pattern. Eventually, the whole tree is traversed in 2 hours by visiting 257,387,474,170 different states using random access memory shared among 576 processing cores. We aim to find specific font patterns among the states of the final depth. However, 83,175,694 of the states are located at the final depth, at which we start looking for font patterns. Before that, a set of 96 characters of size 6 × 6 is binarized, and their (5 × 6)-compatible patterns are taken for lookup by considering all possible symmetries. In this way, a font of 96 characters is designed.

著者

菊地 洋右

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.7, pp.1-4, 2010-09-15

参考文献数

2

---

単純グラフ G のすべての辺を含む路をオイラー路、オイラー路が閉路となっているものをオイラー回路という。オイラー路をもつグラフを semi-eulerian とよび、オイラー回路をもつグラフをオイラーグラフとよぶ。オイラーグラフの特徴付けはグラフ理論の教科書に必ず載っていると言っていいほどよく知られている。オイラーグラフが与えられたときに、オイラー回路の数え上げは #P-完全であることが知られている。本研究は、単純グラフ G がオイラー路をもつとき、重複も抜けもなく、そのオイラー路を列挙するアルゴリズムを提案する。本研究のアルゴリズムではまず Fleury's Algorithm を用いて単純グラフ G のオイラー路を求める。このオイラー路から順次、オイラー路を求めていくことで列挙を行う。提案するアルゴリズムは、Fleury's Algorithm を適用した後に、すべてのグラフ的列を 1 つあたり O(m) 時間で列挙する。For simple graph G, eulerian trail is a trail that has all edges in G. If eulerian trail is close circuit, it is called eulerian circuit. If G has a eulerian trail, G is called semi-eulerian and if G has a eulerian circuit, then G is eulerian graph. A characterization of eulerian graph is well-known and may appear in any graph theory. Given eulerian graph, counting eulerian circuits is #P¡complete. This paper will propose an algorithm to generate all eulerian trail for simple graph G, if such trail exists. At first, we obtain the minimum eulerian trail of G, applying Fleury's algorithm. Next, we generate all eulerian trails. Our algorithm generates all eulerian trails in O(m2) for each, after applying Fleury's algorithm, where m is the number of edge in G.

著者

三溝 和明 朝廣 雄一 宮野 英次

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.4, pp.1-8, 2010-02-26

参考文献数

15

---

本稿では直径 d 部分グラフ最大化問題 (MaxDBS 問題) について考察する.MaxDBS 問題の目的は,入力グラフ G と整数 d≥1 に対して,直径 d である最大部分グラフを G 中から見つけることである.MaxDBS 問題は,d=1 の場合,よく知られた最大クリーク問題と同一であるので,P≠NP の仮定の下で,任意のε>0 に対して n1-ε よりも良い近似度の近似アルゴリズムは存在しない.また d≥2 に対しては,任意の ε>0 に対して n1/3-ε よりも良い近似度の近似アルゴリズムは存在しないことが知られていた.まず本稿では,この結果を改善し,任意の ε>0 に対して n1/2-ε よりも良い近似度の近似アルゴリズムは存在しないことを示す.また,d が偶数の場合には n1/2 -近似アルゴリズム,d が 3 以上の奇数の場合には n2/3 -近似アルゴリズムが存在することを示す.さらに,弦グラフ,スプリットグラフ,区間グラフ,k 部グラフといった制限された入力に対する近似可能性と近似困難性について考察する.The maximum diameter-bounded subgraph problem (MaxDBS for short) is defined as follows: Given an n-vertex graph G and a fixed integer d ? 1, we are asked to find the largest subgraph of the diameter d in G. If d = 1, the problem is identical to the well known maximum clique problem and thus it is NP-hard to approximate MaxDBS to within a factor of n1-ε for any ε > 0. Also, it is known to be NP-hard to approximate MaxDBS to within a factor of n1/3-ε for any ε > 0 and a fixed d ? 2. In this paper, we first strengthen this hardness result; we prove that, for any ε > 0 and a fixed d ? 2, it is NP-hard to approximate MaxDBS to within a factor of n1/2-ε. Then, we show that a simple polynomial-time algorithm achieves an approximation ratio of n1/2 for any even d ? 2, and an approximation ratio of n2/3 for any odd d ? 3. Furthermore, the (in)tractability and the (in)approximability of MaxDBS on subclasses of graphs are discussed for chordal graphs, split graphs, interval graphs, and k-partite graphs.

著者

Asahi Takaoka Shingo Okuma Satoshi Tayu Shuichi Ueno

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2014, no.11, pp.1-6, 2014-11-13

---

The harmonious coloring of a simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem of determining the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are known as caterpillars. This paper shows the harmonious chromatic number of shooting stars and comets, which are ones of the simplest kinds of caterpillar. We also show the upper bound of harmonious chromatic number of 3-regular caterpillars.The harmonious coloring of a simple graph is a vertex coloring such that adjacent vertices are assigned different colors and each pair of colors appears together on at most one edge. The harmonious chromatic number of a graph is the least number of colors used in such a coloring. The harmonious chromatic number of a path is known, whereas the problem of determining the harmonious chromatic number is NP-hard even for trees with pathwidth at most 2. Hence, we consider the harmonious coloring of trees with pathwidth 1, which are known as caterpillars. This paper shows the harmonious chromatic number of shooting stars and comets, which are ones of the simplest kinds of caterpillar. We also show the upper bound of harmonious chromatic number of 3-regular caterpillars.

著者

宇野毅明 中原孝信 前川浩基 羽室行信

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2014-AL-146, no.2, pp.1-8, 2014-01-23

---

近年の IT 技術の発達により,ビッグデータを用いたデータ解析はますますその重要性を増している.しかし,ビッグデータ解析には,データの大きさ以外にも多様性という大きな困難がある.多様なデータは,それぞれ異なる特徴を持つグループから構成されているため,全体的に解析することが困難であり,まずグループ構造の解明が重要である.既存のクラスタリング手法やパターンマイニングによってグループ構造の解明にアプローチすると,解が大量,少数のグループしか見つけられない,類似する大量の解を生成,見つかるグループの大きさに大きなばらつきがある,計算コストが大きすぎる,といった難点にぶつかることになる.本稿では,グラフクラスタリング問題に対して,そもそもデータがどのようになっていればグループ構造が抽出しやすいかを考え,ノイズの少ない明確なデータを定義し,ノイズ混じりの生データを,そのグループ構造を壊さないように明確なデータへと変換する,データ研磨という手法を紹介する.また,データ研磨アルゴリズムとデータ研磨を行ったグラフが持つ数理的な構造を紹介し,将来的に 「明確なデータ」 を研究するための礎とする.

著者

田村 祐馬 伊藤 健洋 周 暁

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2014-AL-148, no.3, pp.1-6, 2014-06-06

---

無向グラフ G のフィードバック点集合 F とは,G から F を取り除くと,残されたグラフが林になるような G の点部分集合のことである.また,F が G の独立点集合をなすとき,F はフィードバック独立点集合という.本稿では,与えられたグラフに対し,点数が最小のフィードバック独立点集合を求める問題について研究する.この問題は,平面的二部グラフに対してさえ NP 困難であることが示せるため,我々はいくつかの特別なグラフクラスに着目する.まず我々は,この問題が木幅制限グラフと弦グラフに対して線形時間で解けることを示す.次に,平面グラフに対しては,解のサイズをパラメータとした FPT アルゴリズムを与える.

著者

保木邦仁

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2012-AL-139, no.5, pp.1, 2012-03-07

---

将棋は西洋のチェスと同じルーツを持つゲームと考えられている。そのため、将棋とチェスのルールには類似点が多い。その一方で、持ち駒ルールのように異なった性質もある。このようなルール上の違いは、人工知能及びアルゴリズム設計の難易度に大きな影響を与えた。実際、IBM ディープ・ブルーが 1997 年にチェスの世界チャンピオンを破った時でも、当時のコンピュータ将棋の棋力は通常のアマチュアプレイヤー以下であった。コンピュータ将棋が人間トップに迫るほどの棋力を獲得したのはごく最近である。2010 年はあから 2010 が清水市代女流王将に勝利し、2011 年には Ponanza が著名なインターネット対局場 (将棋倶楽部 24) の短時間対局で最高レーティングを獲得、また 2012 年にはボンクラーズが米長邦雄永世棋聖に勝利した。本公演では、最近のコンピュータ将棋の動向に加えて、強いプログラムの一つである Bonanza の思考の仕組みを紹介する。高精度評価関数の最適化や、力ずく探索の枝刈り手法について、将棋とチェスの違いを示す。

著者

シュレスタアニシュマンシング 田湯 智 上野 修一

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:18840930)

巻号頁・発行日

vol.2010, no.6, pp.1-7, 2010-11-12

---

It is known that the bandwidth problem is NP-complete for chordal bipartite graphs, while the problem can be solved in polynomial time for bipartite permutation graphs, which is a subclass of chordal bipartite graphs. This paper shows that the problem is NP-complete even for convex bipartite graphs, a subclass of chordal bipartite graphs and a superclass of bipartite permutation graphs. We provide polynomial-time approximation algorithms for convex bipartite graphs. We also provide a polynomial-time approximation algorithm for 2-directional orthogonal ray graphs which is a subclass of chordal bipartite graphs and a superclass of convex bipartite graphs.It is known that the bandwidth problem is NP-complete for chordal bipartite graphs, while the problem can be solved in polynomial time for bipartite permutation graphs, which is a subclass of chordal bipartite graphs. This paper shows that the problem is NP-complete even for convex bipartite graphs, a subclass of chordal bipartite graphs and a superclass of bipartite permutation graphs. We provide polynomial-time approximation algorithms for convex bipartite graphs. We also provide a polynomial-time approximation algorithm for 2-directional orthogonal ray graphs which is a subclass of chordal bipartite graphs and a superclass of convex bipartite graphs.

著者

伊藤 剛志 清見 礼 今堀 慎治 上原 隆平

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.9, pp.1-8, 2009-01-23

---

本稿では 「じゃばら折り」 に関する新しい折り紙の問題を提案する.本問題では与えられた n 個の山折り/谷折りの割り当てに対して,紙をその割り当てに従って等間隔に折ることを目的とする.扱う紙のモデルは以下の通り. (1) 紙は厚み 0 で重ねて一度に複数枚折ることができる. (2) それぞれの折り状態は平坦である. (3) それぞれの折り目はそこで最後に折られたときの折り状態を記憶する. (4) 紙は n 箇所の折り目を除いて剛体である.このモデルにおいて,与えられた割り当てを実現する効率の良い折り操作を見つけることがこの問題の目的である.一般の山谷割り当てに対する問題を単位長折り問題と呼び,山谷割り当てが 「MV MV MV ...」という形をしているときは特にじゃばら折り問題と呼ぶことにする.アルゴリズムの複雑さは折りの回数によって測り,折りを開く回数は無視する.この問題には自明な上界、と自明な下界 log (n + 1) が存在する.本稿ではまず以下の非自明な 2 つの上界を示す. (a) どんな山谷割り当てでも高々 [n/2] + [log (n+1)] 1 回の折りで実現することができる. (b) 任意の ∊>0 に対してじゃばら折りは 0 (n∊) 回の折りで実現することができる.次に以下の非自明な下界を示す. (c) ほとんどすべての山谷割り当ては Ω (n/log n) 回折らなければ作ることができない結果 (b) と (c) より,じゃばら折り問題は単位長折り問題の中では簡単な部類に入ることがわかった.We introduce a new origami problem about pleats foldings. For a given assignment of n creases of mountains and valleys, we make a strip of paper well-creased according to the assignment at regular intervals. We assume that (1) paper has 0 thickness and some layers beneath a crease can be folded simultaneously, (2) each folded state is flat, (3) each crease remembers its last folded state made at the crease, and (4) the paper is rigid except at the n given creases. On this model, we aim to find efficient ways of folding a given mountain-valley assignment. We call this problem unit folding problem for general patterns, and pleats folding problem when the mountain-valley assignment is "MVMVMV…" The complexity is measured by the number of foldings and the cost of unfoldings is ignored. Trivially, we have an upper bound n and a lower bound log [(n+1).] We first give some nontrivial upper bounds: (a) any mountain-valley assignment can be made by [n / 2 ] + [log (n+1) ] foldings, and (b) a pleats folding can be made by O (n∊) foldings for any ∊>0. Next, we also give a nontrivial lower bound: (c) almost all mountain-valley assignments require Ω(log n / n) foldings. The results (b) and (c) imply that a pleats folding is easy in the unit folding problem.

著者

川崎 涼 西村 治道

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09135685)

巻号頁・発行日

vol.2014, no.12, pp.1-8, 2014-06-06

---

Gharibian, Kempe [ICALP2012] は局所ハミルトニアンの冗長性に関する問題 QIRR を導入した.この問題は,局所ハミルトニアンの和が与えられたときにエネルギー期待値の条件を満たした部分和が存在するかを問う問題である.彼らはこの問題が cq-Σp2 困難であることを証明したが,その完全性を示すことはなかった.本論文ではまず,局所ハミルトニアンに関する計算複雑さの高い問題から QIRR への帰着を与え,QIRR が cq-Σp2 に属さない証拠を与える.その後,より適切な形で局所ハミルトニアンの冗長性に関する問題を定義し,再定式化した問題が cq-Σp2 完全であることを示す.Gharibian and Kempe [ICALP2012] introduced a problem on irredundancy of local Hamiltonians, named as QIRR, which asks whether, given a sum of local Hamilitonians, there is a partial sum preserving a given energy constraint. They showed that QIRR is hard for the class cq-Σp2(a quantum analogue of Σp2 ), while they did not show cq-Σp2-completeness. In this paper we first show that QIRR is reduced from some problem that seems too hard to show cq-Σp2-completeness. Then, we introduce another problem on irredundancy of local Hamiltonians in a more suitable form, and show that the problem is cq-Σp2-complete.

著者

中西 裕陽 富田 悦次 若月 光夫 西野 哲朗

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09135685)

巻号頁・発行日

vol.2014, no.14, pp.1-8, 2014-06-06

---

NP 完全である最大クリーク問題に対し,"節点数 n≧1 のグラフにおいて,グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば,最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である." ことを示す.これは,先に発表した結果 (信学論 (D),vol.J97-D,no.6,June 2014) の定量的改良である.This paper presents a further improved extended result for polynomial-time solvability of the maximum clique problem, that is: for any adjacent pair of vertices p and q where the degree of p is less than or equal to that of q in a graph with n vertices, if the degree of p is less than or equal to 3.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm.

著者

橋谷 祐司 櫻川 貴司

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.3, pp.1-8, 2010-02-26

参考文献数

7

---

本稿では,確率的アルゴリズムを用いた場合における No Free Lunch 定理 (NFL定理) を厳密に証明する.NFL 定理からは 「どのような最適化問題に対しても効率良く解を導き出す万能の探索アルゴリズムは存在しない」 ということを示唆する定理であり,多くの最適化問題や探索アルゴリズムについての研究論文に引用されている.NFL 定理は 「どのような最適化問題に対しても効率良く解を導き出す万能の探索アルゴリズムは存在しない」 ということが帰結される定理で,多くの最適化問題や探索アルゴリズムについての研究論文に引用されている.本稿では確率的アルゴリズムを形式的に定義し,いくつかの補題を示した上で確率的アルゴリズムの場合の NFL 定理を確率論によって厳密に証明する.In this paper, a rigorous proof of No Free Lunch Theorem (NFLT) for stochastic algorithms is presented. NFLT shows that there is no algolithm which can solve every optimization problem efficiently. A lot of research papers on optimization problems and search algorithms refer to it. We give a formal definition of stochastic algorithm, prove some lemmas and then complete a regourous proof of NFLT for stochastic algorithms using probability theory.

著者

上原 隆平

雑誌

研究報告アルゴリズム(AL)

巻号頁・発行日

vol.2010-AL-131, no.11, pp.1-3, 2010-09-15

---

近年,計算幾何学の一部で 「計算折紙」 とよばれる分野が注目を集めている.その分野では,ある意味で折紙を計算のプラットフォームとみなしている.こうしたプラットフォーム上で,計算量理論的に手におえない困難な問題や,多項式時間で解ける問題がいくつか知られている.さてチューリング機械といった標準的な計算モデルにとって,決定不能な問題の存在は,その計算モデルの計算能力の高さを逆説的に示しているといえよう.それならば,計算折紙モデルでは決定不能な問題が存在するだろうか?本稿では,この疑問に対する解答を与える.具体的には,計算折紙モデルのごく自然な決定問題が決定不能であることを示す.

著者

沖 忠親 田岡 智志 渡邉 敏正

出版者

情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2010, no.7, pp.1-8, 2010-02-26

---

2 部グラフの k 辺連結化問題 (以下,UW-Bipartite- (k+1) ECA (*, MA) と略記) は以下のように定義される: 「無向 2 部グラフ G = (V + ∪V-,E) が与えられたとき,辺付加後のグラフ G' = (V + ∪V- ,E∪E') が (k + 1) 辺連結 2 部グラフであるような最小の付加辺集合 E' を求めよ.」本稿では,G が k 辺連結であるときに最適解を算出する高速アルゴリズムを提案し,k ∈ {1, 2} のとき線形時間で解けることを示す.The k-edge-connectivity augmentation problem of bipartite graphs (UW-Bipartite-kECA(*, MA) for short) is defined as follows: "Given an undirected bipartite graph G = (V+ ∪V-,E), find a smallest set E' of edges such that G' = (V+ ∪V-,E∪E') is a k-edge-connected bipartite one." In this paper we propose a fast algorithm for finding an optimum solution to UW-Bipartite-(k + 1)ECA(*, MA) when G is k-edge-connected with k > 0, and show that it can be solved in linear time for k ∈ {1, 2}.

著者

泉 朋子 泉 泰介 小野 廣隆 和田 幸一

出版者

一般社団法人情報処理学会

雑誌

研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2009, no.18, pp.49-56, 2009-02-26

---

証明書分散問題(Minimum Certificate Dispersal Problem, MCD)とは,グラフGと要求集合Rが与えられたときに,Rに含まれるすべての要求を満たすよう各ノードにGの辺を割り当て,各ノードに割り当てられる辺の総数を最小化する問題である.要求とはグラフG上の異なる2つのノードの順序対で表され,要求(u, v)を満たすにはノードu, vに割り当てる辺の和集合にGにおけるuからvへの経路が含まれる必要がある.MCDは与えられるグラフが強連結の場合においてもNP-困難であることが既に示されている.本研究では,MCDの近似可能性について議論する.まず,強連結グラフにおいてMCDの近似率の下界がOmega(log n)(nはGのノード数)であることを示し,さらに任意のグラフにおけるMCDに対する多項式時間O(log n)-近似アルゴリズムが構成可能であることを示す.また,既存研究において多項式時間2-近似アルゴリズムであると評価されていたアルゴリズムが,無向グラフを入力とするMCDに対しては多項式時間3/2-近似アルゴリズムであることを示す.Assume that G is a graph and that R is a set of requests which is represented by a reachable ordered pair of nodes in G. The problem discussed in this paper requires us to assign edges to each node such that all requests in R are satisfied and the total number of edges all nodes have is minimized for a given G and R. To satisfy a request (u, v), a set of assigned edges to u and v must contain a path from u to v in G. This problem is called the Minimum Certificate Dispersal problem (MCD) and is NP-hard even if the input graph is restricted to a strongly connected one. In this paper, we consider approximability of MCD. We clarify an optimal approximability / inapproximability bound in terms of order: we prove the approximation ratio of MCD for strongly connected graphs is Omega (log n) and MCD has a polynomial time approximation algorithm whose factor is O(log n) (n is the number of nodes in G). In addition, we prove that when a given graph is restricted to an undirected graph, the MCD algorithm proposed in [11] guarantees 3/2 approximation ratio.