ネットワーク上の並列-分散アルゴリズムに関する研究

网络并行分布式算法研究

• 批准号: 08780234
• 负责人: 鈴木 均
• 金额: $ 0.64万
• 依托单位: Ibaraki University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780234/
• 关键词: 平面グラフ; 最短路; 計算幾何学; 平面; 非交差道; VLSI

いくつかのグラフ・ネットワーク上の問題を解く効率の良いアルゴリズムを開発した.以下が主な成果である。1.VLSIの1層配線問題には,2次元平面領域においていくつかの端子対を結ぶ互いに交差しない長さの総和が最小な道を求める問題がよく現われる.ここで"交差しない"とは,同じ点や線分を通るかもしれないが平面上では交差しないことである.一方,平面領域上の問題の多くが平面グラフ上の問題に帰着される.本研究では平面グラフの2つの面の周上にいくつかの端子対が指定されている場合にそれらの端子対を結ぶ"交差しない"道で長さの総和が最小であるものを求めるアルゴリズムを与えた.アルゴリズムの計算時間はO(nlogn)である.ここで,nはグラフの点数である.2.平面上で指定した2点の結び障害物を通らない道で長さが最小なものを求める問題はさまざまな場面で現われる.本研究では障害物の形状を軸平行多角形に限定し,先に障害物が与えられて前処理が可能である場合のアルゴリズムを与えた.前処理に要する時間はO(n^2log^2n)であり,2点が与えられた時にそれらを結ぶ最短路をO(log^2n)時間で求めることができる.

The problem on the Internet is solved and the problem is solved. The following is the main result. 1. VLSI 1-layer wiring problem, 2-dimensional plane domain, terminal pairs, junctions, intersections, long sum, minimum path problems, etc. "Cross difference" One side, many problems on the plane field, many problems on the plane field. In this study, the terminal pairs are specified on the circumference of the plane and the surface of the plane, and the terminal pairs are specified on the occasion of the intersection of the terminal pairs. O(nlogn). 2. On the plane, specify 2 points of junction and obstacle, pass through the path, find the smallest problem, find the scene. In this study, the shape of the obstacle is limited by the parallel polygon of the axis. The time required for pre-processing is O(n^2log^2n)

项目成果

Junya Takahashi: "Shortest noncrossing paths in plane graphs" Algorithmica. 16. 339-357 (1996)

Junya Takahashi：“平面图中最短的非交叉路径”算法。

岩井誠: "軸平行多角形障害物がある平面上の最短路" 電子情報通信学会論文誌D-1. J79-D-I・7. 409-415 (1996)

Makoto Iwai：“具有轴平行多边形障碍物的平面上的最短路径”电子、信息和通信工程师学会会刊 D-1 J79-D-I・7（1996）。