著者

千田 栄幸 静谷 啓樹 西関 隆夫

出版者

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

雑誌

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ

巻号頁・発行日

vol.94, no.137, pp.1-10, 1994-07-11

---

「f(x),f(y)が与えられたとき,f(x+y)とf(x・y)の両方を効率的に計算できるような暗号化関数fは,存在するか?」現在のところ,このような関数fの存在は知られておらず,暗号理論分野における未解決問題の一つとなっている.環準同型が暗号化関数となるならばこの解となりうるので,これまでは,基礎検討として半分配環上の一方向性関数について考察を行ってきた.本文では,一方向性群準同型と一方向性環準同型の関係について考察し,群準同型の性質を持つ暗号化関数について一方向性であることがいえれば,一方向性環準同型が存在することを示す.また,上記の未解決問題を一般の加法と乗法に拡張した場合に対する肯定的な解を与える.

著者

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

出版者

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

雑誌

電子情報通信学会技術研究報告. 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, コンピュテーション

巻号頁・発行日

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

---

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

著者

金丸 直義 西関 隆夫 浅野 哲夫

雑誌

情報処理学会研究報告アルゴリズム(AL)

巻号頁・発行日

vol.1992, no.27(1991-AL-026), pp.25-32, 1992-03-23

---

本報告では,与えられた凸m角形内部のすべての整数格子点を列挙するO(+m+log )時間のアルゴリズムを与える.ここでKは列挙された格子点の個数であり,nは凸m角形の大きさ,すなわちm角形を包含する軸平行な長方形の垂直,水平な辺のうち短い方の長さである.さらに,m個の制約式を持つ2変数整数計画問題を解くO( log m+log )時間のアルゴリズムを与える.ここでnは計画問題の許容解空間である凸多角形の大きさを表す.このアルゴリズムは従来知られているアルゴリズムより単純であり,時間計算量も改善している.