著者

堀山 貴史 樋口 康介

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.109, no.108, pp.17-21, 2009-06-22

参考文献数

22

---

最長路問題は、各辺に非負整数の距離が与えられた無向グラフに対し、始点s、終点t間のシンプルなパスで、その上の距離の総和が最大となるものを求める問題である。最長路問題は、効率的な多項式時間アルゴリズムが古くから知られている最短路問題とは異なった性質を持つ。例えば、各辺に関連付けられた距離の正負を反転させた最短路問題を解くことで最長路が得られるように一見思われるが、負の閉路(距離の総和が負となる閉路)が存在するため、最短路問題のアルゴリズムを適用することはできない。本研究では、最長路問題、s-t最長路問題、全点対最長路問題を定式化し、全探索および0-1整数計画法に基づく厳密最適化アルゴリズムを提案する。また、JR大都市近郊区間の大回りをベンチマークとして利用し、各手法の実装および評価を与える。

著者

中島 孝明 藤原 暁宏

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.431, pp.1-6, 2001-11-09

参考文献数

9

---

本稿では, 並列化困難な問題として知られているP完全問題の一つである, スタックを用いた幅優先探索の並列性について検証する.まず, 入力グラフの最大次数が3であるようなスタックを用いた幅優先探索もP完全となることを示す.次に, スタックを用いた幅優先探索のP完全性を表す尺度として最長経路距離を導入し, この尺度を用いて, 効率の良い並列アルゴリズムの提案を行う.このアルゴリズムの計算量により, l=O(log^n)の場合, スタックを用いた幅優先探索がクラスNCに属することを示す.ここで, n, lはそれぞれ入力サイズおよび最長経路距離であり, kは正の整数とする.また, このアルゴリズムはl=O(n^ε), 0<ε<1の場合にコスト最適な並列アルゴリズムとなる.

著者

浅野 哲夫 ムルツァー ウォルフガング ロウテ ギュンター ワング ヤジュン

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.110, no.232, pp.1-7, 2010-10-08

---

本報告では定数作業領域あるいは対数記憶領域と呼ばれる制約のある計算モデル上で効率よく実行できる幾何問題に対するアルゴリズムを提案する.まず最初に平面上に与えられた点集合に対するデローネイ三角形分割を描くアルゴリズムから始め,それをボロノイ図を描く問題に応用する.これらの問題に対しては,O(n)の記憶領域を用いることができるならΘ(n log n)時間のアルゴリズムが知られているが,本報告で述べるアルゴリズムはO(1)の作業領域だけを用いてO(n^2)時間で実行できるものである.さらに,これらのアルゴリズムを用いて,平面上に与えられた点集合に対するユークリッド最小木を求める効率の良いアルゴリズムも与える.

著者

岡本 和也 宮崎 修一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.110, no.325, pp.45-51, 2010-11-26

---

座席予約問題では駅s_1から駅s_kまでのk駅に停まるn席の座席を持った列車を考える.各乗客は出発駅s_iから到着駅s_j(1≦i≦j≦k)までのチケットを要求する.オンラインアルゴリズムは,未来の要求を知らずに各乗客をn席の座席の1つに割り当てる必要がある.座席予約問題の目的はチケットの売上合計額を最大化することである.チケットの価格設定により,座席予約問題には2つのモデルがある.一つは単一価格問題であり,もう一つは比例価格問題である.我々は,両方のモデルにおいて,競合比の上下限を改良した.単一価格問題に関しては,上限を8/(k+5)から4/(k-2√<k-1>+4)に改良した.また,Worst-Fitアルゴリズムの上限も4/(k-1)から2/(k-2√<k-1>+2)に改良した.さらに,比例価格問題に関しては,上限を(4+2√<13>)/(k+3+2√<13>)((&sime;11.2/(k+10.2))から(3+√<13>)/(k-1+√<13>)((&sime;6.6/(k+2.6))に改良し,下限を1/(k-1)から2/(k-1)に改良した.

著者

朝廣 雄一 伊藤 健洋 江藤 宏 宮野 英次

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.113, no.198, pp.43-50, 2013-08-27

---

本稿では,グラフG=(V, E)と指定次数γが与えられたとき,頂点部分集合S によって誘導される部分グラフG[S]が指定した次数rの正則グラフであり,頂点数が最大となるようなSを見つけ出す最適化問題を考える.また,グラフG[S]がr-正則,かつ連結グラフである場合についても考える.両問題は,ある定数rについて,近似することさえNP困難であることが知られている.本稿では,入力を特別なグラフクラスに限定した問題について考える.rをある定数とし,入力グラフを二部グラフまたは平面グラフに限定したとしても,本稿で考える連結性を条件とする正則誘導連結部分グラフ探索問題と必要としない正則誘導部分グラフ探索問題が近似することさえNP困難のままであることを示す.一方,以下のような木構造を持つグラフを入力とした場合には,両問題が簡単になることを示す.まず,木幅限定グラフを入力としたとき,両問題に対する最適解を線形時間で求めるアルゴリズムを示す.ここで,計算時間に隠れている係数は木幅の単一指数である.更に,入力を弦グラフとしたときには,両問題の最適解を多項式時間で求めることができることを示す.

著者

高村 政孝 五十嵐 善英

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.376, pp.61-68, 2001-10-12

被引用文献数

1

---

本論文ではsingle-writer/multi-reader共有変数モデル上で相互排他問題を解く2つのアルゴリズム提案する.これらのアルゴリズムはBakery algorithmの改良である.まず, ある特殊な条件が成り立っている元で, 有限サイズの共有変数で相互排他が実現されるようBakery algorithmを変更する.次に, この特殊な条件を取り除くために, どのユーザーにも属さない追加のプロセスを用いたアルゴリズムを提案する.この追加のプロセスを用いた相互排他アルゴリズムはlock-out-freeを満足する.さらに, このアルゴリズムの共有変数のサイズを減らすよう改良したアルゴリズムも提案する.これらのアルゴリズムの時間計算量は, ユーザーの数をn, atomic stepの時間の上限をl, ユーザーが資源を利用する時間の上限をcとすると, いずれも(n-1)c+Ο(nl)である.共有変数のサイズは, 最初のアルゴリズムが(n+1)(1+⌈log(n+2)⌉bits, 二つ目のアルゴリズムがn(1+⌈log(n+1)⌉)+1bitsである.

著者

桝田 秀夫 増澤 利光 辻野 嘉宏 都倉 信樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.94, no.389, pp.11-18, 1994-12-09

被引用文献数

2

---

ネットワークの取り得る全状況集合をSとし,そのうち望ましい状態とみなせる状態の集合を正当な状況といい,Lと表す(L⊆S).任意のSの状態から出発し有限時間内にLに含まれる状態に達する分散アルゴリズムを自己安定アルゴリズムという.従来,自己安定アルゴリズムは,プロセッサ同士が通信路として2点間通信(Point-to-Point)リンクを用いて情報を交換するネットワークモデル上で考えられてきた.本稿では,マルチアクセスチャネルを持つネットワーク上でリーダー選択問題を解く自己安定分散アルゴリズムを提案する.

著者

ラハマン モハマッド サイドゥル 中野 眞一 西関 隆夫

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.98, no.380, pp.1-8, 1998-10-30

---

平面グラフGを整数格子上に次の(1)-(3)を満たすように描画したものをGの箱-矩形描画という.(1)各点は矩形として描画する.(この矩形を箱と呼ぶ.)(2)各辺は水平もしくは垂直線分として描画する.(3)各面の輪郭は矩形として描画する.平面グラフGの描画で, 各点を格子点として描画し, 各面の輪郭を矩形として描画したものを, Gの矩形描画という.箱-矩形描画は, 通常の矩形描画の自然な一般化である.本論文では, 平面グラフGが箱-矩形描画を持つための必要十分条件を与える.また, Gが箱-矩形描画を持つならば, その描画を求める線形時間アルゴリズムも与える.求められた描画の高さと幅の和は, m+2以下である.ここで, mはGの辺数である.

著者

藤戸 敏弘 奥村 将

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.101, no.184, pp.17-24, 2001-07-09

---

集合被覆問題とは、集合Uの(コストつき)部分集合の族が与えられ、Uの任意の要素が、その部分集合により被覆される(含まれる)ような、最小コストの部分族を計算する最適化問題である。又、与えられる部分集合の大きさがある定数κ以下の場合には、κ集合被覆問題と呼ばれる。同問題に対しては、近似保証がH(κ)=Σ^κ_<i=1>(1/i)の解が貪欲法により求まることが、よく知られているが、部分集合コストが一定である場合を除き、より良い近似保証は知られていない。そこでまず手始めとして、部分集合コストが1ないし2に限定されたκ集合被覆問題を、本稿では対象とする。貪欲法を適切に改良することで、3-集合被覆問題に対してはH(3)-1/6, κ-集合被覆問題に対してはH(κ)-1/12, という近似保証の得られることを、線形計画緩和とその双対を用いて示す。

著者

打矢 泰志 中村 篤祥 工藤 峰一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.109, no.195, pp.13-20, 2009-09-07

---

Auerらにより研究されたadversarial bandit問題は,プレーヤーが選択したアクションに対する報酬生成過程において確率的な仮定をおかないmulti-armed bandit問題である.本稿ではadversarial bandit問題を,各時刻においてk(≧1)回のアクションを選択できるように拡張し,アクションの重複選択を許す場合と許さない場合の2つの設定で分析を行う.両方の設定において,Auerらが提案したアルゴリズムExp3を一般化し,最適固定アクション集合に対する損失上界の一般化を得る.

著者

猪飼 武夫 益本 昌幸 福永 邦雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.95, no.374, pp.45-54, 1995-11-17

被引用文献数

5

---

有限オートマトン(FA)を離散時間動的システムと捉えて状態と記号の{0,1}上の符号化とシステム特性(状態推移関数など)のパラメータ化により、FAの状態空間モデルが得られる。この状態も出る表現に基づく決定性FA(DFA)学習では、従来の記号学習に代りパラメータ同定となる。本報告ではDFAに対し、可到達性および可観測性を定義した上で、DFAの入出力応答(特性応答)から構成するハンケル行列からのDFAの最小表現法を確立し、さらに部分、ハンケル行列からの最小部分実現のアルゴリズムも導出している。

著者

ラハマン モハマド サイドゥル 西関 隆夫 ゴーシュ シュバシシュ

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.102, no.258, pp.21-28, 2002-07-29

---

平面的グラフは平面上への埋め込みが固定されておらず,いろいろな埋め込みがありえる.一方,埋め込みが固定された平面的グラフは平面グラフと呼ばれる.平面グラフの矩形描画では,各点は平面上の点として描かれ,各辺は水平あるいは垂直線分として描かれ,各面は矩形として描かれる.平面的グラフの少なくとも1つの平面埋め込みが矩形描画を持つならば,その平面的グラフは矩形描画を持つという.本論文では最大次数が3の平面的グラフGが矩形描画を持つかどうかを判定し,もし持つならばGの矩形描画を求める線形時間アルゴリズムを与える.

著者

大隅 剛史 伊藤 大雄 岩間 一雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.16, pp.31-36, 2004-04-15

---

近年のよく知られたWebグラフの問題の1つとして、グループ内で密にリンクされているWebページのグループを見つける問題がある。クリークは明らかにそのようなグループの例と言える。しかしクリークを求める問題(最大のものを求める、極大のものを列挙する)のほとんどは難しく、良い近似方法もない。本稿では「孤立した」クリークとその一般化として孤立した部分グラフを紹介する。部分グラフが「孤立している」とは、内部で密にリンクされているだけでなく、その部分グラフと外部とのリンクが少ないことをいう。例えば、サイズだのクリークでは、外部への枝はκ-1本以下しか許されない。このような孤立条件により、多くの問題が簡単になり、孤立したクリークを列挙する問題が多項式時間で解くことができる。また、孤立したクリークよりやや密度の低い準クリークについても、平均次数がκ-logだ以上でかつ最小次数がκ/(logκ)以上である準クリークを多項式時間で列挙できることを示す。さらにこれらの一般化として、連結度を利用して孤立した一般の部分グラフを多項式時間で列挙できることも示す。

著者

田口 敬教 都倉 信樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.106, no.405, pp.23-28, 2006-11-27

参考文献数

5

被引用文献数

1

---

流通商品コード(単品識別)表示用などに広く利用されるコードにEANコードというものがある.EANコードは白と黒の線で表現されており,バーコードスキャナなどで読み込む.汚れなどの外的要因やスキャンしたデータのディジタルデータへの変換過程での誤りなどの要因により,本来EANコードの表しているデータと異なるデータを読み込んだ場合,それがEANコードの形式に反するなら誤りと判断でき,再読込をする.しかし,形式的には正しいとして誤ったデータを受け取ることもある.これを誤りを見逃し,あるいは誤読といい,その確率を評価する.

著者

杉本 琢磨 堀山 貴史

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.110, no.232, pp.19-25, 2010-10-08

---

Vickreyオークションでは,第一価格を入札した者が,第二価格で商品を落札する.このオークションは,入札者に対し誘因両立性を持つことが知られている.一方,入札者のプライバシーに配慮して,各入札者の入札額や誰が落札したかを入札者には伏せたまま実行する場合には,競売人が落札者に対して第二価格を偽ることができる.本研究では,秘密分散を用いることで,競売人の不正を許さず,全体の半分未満の参加者がsemi-honestな参加者として結託したとしても情報を漏らさない情報理論的に安全なプロトコルを提案する.このプロトコルは,入札者が直接情報のやり取りを行うことで,第三者機関を必要としないことが特長である.さらに,第一価格入札者が複数存在した場合のタイブレークの方法,オークションの結果が正当であり競売人による不正が無かったことを入札者に納得させる方法を提案する.

著者

松原 渉 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.110, no.12, pp.39-45, 2010-04-15

---

移調を許したマッチングとは,与えられたテキストとパタンに対して,任意のオフセットを許した移調パタンの出現を発見する問題であり,例として音楽検索が挙げられる.本研究では,移調を一般に文字の置き換え関数としてとらえ,任意の置換が与えられたとき,すべてのパタンを検出する問題について取り組む.入力のテキストとパタンは,文法圧縮の一種である直線的プログラム(SLP)で与えられるものとし,文字列を陽に展開することなく処理を完了する効率の良いアルゴリズムを与える.

著者

松原 渉 稲永 俊介 篠原 歩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.108, no.443, pp.9-16, 2009-02-23

---

平衡直線的プログラム(Balanced Straight line program,BSLP)は単元集合を生成する文脈自由文法とみなすことができ,そこで生成される文字列の長さNは,変数の個数nに対して指数的に長くなりうる.そのため,BSLPによって圧縮表現された文字列に対してnの多項式時間で効率よく処理を行うには,陽に展開することなく処理を行うことが必要不可欠となる.本研究では,BSLPとして表現された文字列の非反復性判定をO(max(n^2,nlog^2N))時間,O(n^2)領域で解くアルゴリズムを示す.

著者

石原 啓子 平石 邦彦

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.96, no.585, pp.41-50, 1997-03-17

---

最近、線形論理とペトリネットとの間の関係を調べる研究がされており、種々の結果が得られている。線形論理はresource consciousな論理であるということより、むしろ並行性を表すのに非常に有効な論理であると考えられている。線形論理において、ペトリネットのplaceとtransitionはそれぞれ論理式と証明可能性に関係づけられる。EngbergとWinskelは、直観主義線形論理のモデルとして、直接ペトリネットからquantaleを生成することにより双方の関係を調べた。彼らは、このペトリネットより生成されたquantaleに対する、直観主義線形論理の健全性を示したが、完全性の証明は示していなかった。ここで我々は、ペトリネットよりquantaleを生成する新たな方法を示し、直観主義線形論理の完全性を証明した。

著者

田中 圭介 西野 哲朗

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション

巻号頁・発行日

vol.94, no.26, pp.51-60, 1994-04-27

---

否定数限定回路とは,回路中で使用できるNOTゲートの個数をlog(n+1)に制限した組合せ回路である.本稿では,n変数を反転する否定数限定回路(反転回路)の複雑さについて考察する.本研究以前に知られている反転回路のサイズの最良の上界は,O(n^2(logn)^2)である.本稿ではまず,この上界をO(n(logn)^2)に改良できることを示す.次に,反転回路のサイズと深さに関してそれぞれ,5n+3log(n+1)-6および4log(n+1)+2の下界を示す.さらに,n変数を反転する否定数限定回路にある種の制約を加え,その回路サイズが超線形下界をもつような二つの特殊な場合を紹介する.

著者

今井 桂子 河村 彰星 徳山 豪 マトウシェク イルジ レエム ダニエル

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.109, no.391, pp.17-22, 2010-01-18

---

距離空間内の空でない二集合P,Qから等距離にある点の全体をP,Q間の距離二等分という.列 C_1,…,C_<k-1>であって各C_iがC_<i-1>とC_<i+1>との距離二等分であるもの(但しC_0=P,C_k=Qと考える)をP,Q間の距離k等分という.この概念は回路設計についての村田の問をもとに浅野,マトウシェク,徳山が導入し,PとQとがユークリッド平面内の点でありkが3であるときに限りその存在と唯一とを既に示した.本稿ではより一般に固有測地空間内の空でなく交らない二閉集合間に距離k等分が存在することを示す(一意性は不明).証明においては,二集合間のk階層という概念を定義し,その存在をタルスキ不動点定理によって示す.これはレエム,ライクが似た問題に対して用いた手法である.