ネットワーク上の効率の良い種々のアルゴリズムに関する研究

网络上各种高效算法的研究

• 批准号: 07780213
• 负责人: 鈴木 均
• 金额: $ 0.58万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780213/
• 关键词: グラフ; ネットワーク; アルゴリズム; CAD; 計算幾何学; 最短路

いくつかのグラフ・ネットワーク上の問題を解く効率の良いアルゴリズムを開発した.以下が主な成果である.1.VLSIの1層配線問題には,2次元平面領域においていくつかの端子対を結ぶ互いに交差しない長さの総和が最小な道を求める問題がよく現われる.ここで“交差しない"とは,同じ点や線分をとおるかもしれないが平面上では交差しないことである.一方,平面領域に長方形の障害物の他に2層配線領域がある場合に,指令された2組の端子対を結ぶ道で,2層配線領域以外では互いに交差せず,長さの和が最小なものを求める問題はVLSIの2層配線問題に現われる.本研究では,この問題を解くO(nlogn)時間のアルゴリズムを与えた.ここで,nは長方形障害物と2層配線領域の総数である.2.平面上にいくつかの障害物がある場合に指定した2点を結び障害物を通らない道で長さが最小なものを求める問題はさまざまな場面で現われる.本研究では障害物の形状を軸平行多角形に限定し,先に障害物が与えられて前処理が可能である場合のアルゴリズムを与えた.前処理に要する時間はO(n^2log^2n)であり,2点が与えられた時にそれらを結ぶ最短路をO(log^2n)時間で求めることができる.3.直並列グラフや部分k-木上の多くの組み合わせ問題は線形時間で解けるが,辺彩色問題は直並列多重グラフ上でも今までに多項式時間のアルゴリズムが知られてない数少ない問題である.本研究では直並列多重グラフ上で辺彩色問題を線形時間で解く逐次アルゴリズムとO(log|V|)時間で解く並列アルゴリズムを与えた.ここでVは与えられる直並列多重ブラフの点集合である.この結果はスケジューリング問題を解く上で有用である.

The problem on the Internet is solved and the problem is solved. The main results are as follows: 1. VLSI 1-layer wiring problem, 2-dimensional plane domain, terminal pairs, junctions, intersections, lengths, and minimums.ここで“交差しない"とは,同じ点や缐分をとおるかもしれないが平面上では交差しないことである. In case of rectangular barrier in one plane area and other 2-layer wiring area, the command is for 2 groups of terminal pairs, and in case of 2-layer wiring area, the intersection difference is for 2 groups of terminal pairs, and the sum is for 2 groups of terminal pairs. In this paper, we study the problem O(n log n) time. The total number of rectangular obstacles in 2-layer wiring field is In this study, the shape of the obstacle is limited by the parallel polygon of the axis. Pre-processing requires time O(n^2log^2n) In this study, the linear time of the color problem is O(log).| V| The time is right.ここでVは与えられる直并列多重ブラフの点集合である. The result is that the problem is solved.

项目成果

Yoshiyuki Kusakari: "Finding a shortest pair of paths on the plane with obstacles and Crossing areas" Lecture no tes in computer scieree. 1004. 42-51 (1995)

Yoshiyuki Kusakari：“寻找飞机上有障碍物和交叉区域的最短路径对”计算机科学讲座笔记。

草刈 良至: "障害物と交差領域のある平面上での最短な2本の道" 日本応用数理学会論文誌. 5. 381-398 (1995)

Yoshihisa Kusakari：“有障碍物和相交区域的平面上的两条最短路径”日本应用数学学会汇刊 5. 381-398 (1995)。

Xiao 2hou: "A linear algorithm for edqe-coloring series-parallel myltigraph" Journal of Algorithms. (掲載決定). (1996)

肖2侯：“edqe-着色系列并行myltigraph的线性算法”算法杂志（1996年出版）。