著者

川口 喜三男 呉敬軍 和田 幸一

出版者

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

雑誌

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

巻号頁・発行日

vol.1993, no.48, pp.119-126, 1993-05-28

---

一定の面積の自動倉庫を十分利用するためにより多くの部品を保管し,かつ効率よい出荷作業が要求されている.それを実現するために,平面自動倉庫に置ける荷台の移動操作の最小歩数についての研究がなされている.本論文は,未だ解決されていない三つの空位を持つN×M(≧)平面自動倉庫において任意の位置にある荷台を自動倉庫の出口まで移動するのに要する最小歩数関数を決定する.又,M=2の場合の最小歩数関数は一般の場合の解においてM=2と置く事によっては解は得られないので,M=2の場合に対して最小歩数関数を別個に決定する.The minimum number of sliding operations (steps) for moving a palette in an automatic warehouse was considered. In this paper, we consider the function of the minimum number of steps for a palette at any position in the aotumatic warehouse of size N×M(M≧2) with three spaces to be moved to the exit of the automatic warehouse.

著者

和田 幸一 萩原 兼一 都倉 信樹

出版者

電子通信学会

雑誌

電子通信学会論文誌 D (ISSN:0374468X)

巻号頁・発行日

vol.68, no.5, pp.p1011-1018, 1985-05

---

VLSIチップを平面格子と呼ばれるグラフでモデル化し,回路を素子間の配線の仕方を表すグラフGで表し,Gを平面格子に埋込んだとき,どれほどの面積を占めるかはVLSIチップの設計においては重要な問題であり,種々のグラフに対して,平面格子に埋込んだときの面積の上下界が議論されている.本論文では,次数が5以上のグラフが埋込めるように拡張したモデルのもとで,d次シャフルグラフを平面格子に埋込む問題を考える.d次シャフルグラフはシャフルエクスチェンジグラフやCCCなどと同様にデータの置換などを高速に行なうことができ理論的にも興味深いグラフである.ここでは,グラフの交差数と面積の関係を用いて,無限個のd,kに対して,dk頂点d次シャフルグラフを埋込むために(dk+1/k)2に比例した面積が必要となることを示す.この結果を用いると従来の面積の下界が改善される.また,あるグラフGの埋込みに対して,すでに埋込み面積がわかっているグラフを利用したGの埋込みの手法を与え,この結果を用いて,dが2のベキ乗の場合,dk頂点d次シャフルグラフは(dk+1/k)2に比例した面積で埋込めることを示す.

著者

J.ホロムコヴィッチ著 和田幸一 増澤利光 元木光雄訳

出版者

丸善出版

巻号頁・発行日

2012

著者

和田 幸一

出版者

社団法人情報科学技術協会

雑誌

情報の科学と技術 (ISSN:09133801)

巻号頁・発行日

vol.51, no.4, pp.208-212, 2001-04-01

---

図書館員は, 米国でさえ準専門職とされている。専門職の要件に沿って, 米国と日本の大学図書館員を比較したところ, 少なくとも教育, 資格, 自律性の点で明らかに日本の大学図書館員は, 専門職の度合が低いことがわかった。一方, 業務区分・何をもって専門職とするかの困難さ, 終身雇用制の存在, 社会奉仕の概念の欠如から, 日本の専門職化が困難であることを指摘した。そして, 筆者が目の当たりにした米国の専門職制の背景として, (1)専門職というラベルがポジションにつけられていること, (2)社会への大学図書館の奉仕, (3)図書館員が図書館界全体を育てていくという意識の存在を紹介した。

著者

片山 喜章 高橋 直久 和田 幸一 高橋 直久 和田 幸一

出版者

名古屋工業大学

雑誌

基盤研究(C)

巻号頁・発行日

2007

---

無線通信装置を有する大量のセンサー端末が互いに通信しあうネットワークがセンサーネットワークであり,これは一般の無線通信端末による"アドホックネットワーク"(無線通信ネットワーク)として捉えることが可能である.本研究では,アドホックネットワーク上で効率のよい通信を実現するための論理的構造の構築方法と経路制御手法,および端末が自律的に移動する場合にそのシステムがどのように制御可能かを明らかにした.これらの成果を,7編の論文,8件の国際会議,および学術誌解説記事と招待講演各1件で発表した

著者

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

出版者

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

雑誌

研究報告アルゴリズム(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.

著者

内田 次郎 MuzahidulA.K.MIslam 稲葉 直貴 片山 喜章 陳慰 和田 幸一

出版者

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

雑誌

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

巻号頁・発行日

vol.2006, no.49, pp.33-40, 2006-05-18

---

センシング機能、通信機能を備えた小型センサーデバイスから構成されるネットワークをセンサーネットワークという。センサーネットワークに対し、"オーバーヘッドやエネルギー消費量の最小化"などの利点を持つアーキテクチャの構築方法としてクラスタリングが挙げられる。本研究では、[2]で提案されているアーキテクチャが持つ望ましい性質を維持しつつ改良を加え、タスクの完了時間やその拡張などの面においてよりよい性質を持った三つのアーキテクチャおよびそのメンテナンスのためのアルゴリズムを提案する。A sensor network is a collection of transmitter-receiver devices (referred to as nodes). Clustering is seen as the step to provide the flat sensor network topology with a hierarchical architecture with properties such as minimizing communication overhead and minimizing the overall power consumption. In this paper we improve the architecture [2] maintaining the desirable properties and propose three architecture and maintenance algorithms which has the better properties about the completion time of tasks, expansions of tasks, and so on.