权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

グラフとネットワーク上の効率の良い並列アルゴリズムに関する研究

图与网络高效并行算法研究

基本信息

批准号：
06780222
负责人：
鈴木均
金额：
$ 0.58万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780222/
关键词：
グラフネットワークアルゴリズム VLSI スケジューリング配線 CAD 彩色

项目摘要

いくつかのグラフ・ネットワーク上の問題を解く効率の良い逐次・並列アルゴリズムを開発した.以下が主な成果である.1.直並列グラフや部分k-木上の多くの組み合わせ問題は線形時間で解けるが,辺彩色問題は直並列多重グラフ上でも今までに多項式時間のアルゴリズムが知られてない数少ない問題である.本研究では直並列多重グラフ上で辺彩色数を線形時間で求め,さらにO(|V|log|E|)時間で具体的な辺彩色を求める逐次アルゴリズムを与えた.また辺彩色問題をO(log|V|)時間で解く並列アルゴリズムも与えた.ここでVとEはそれぞれ与えられる直並列多重グラフの点集合と辺集合である.この結果はスケジューリング問題を解く上で有用である.2.外長方形とその内部の1つの長方形(内長方形)で囲まれた平面領域をAとする.Aの内部にはγ個の長方形障害物があるとする.外長方形と内長方形の周上にk組の端子対が指定されているとする.本研究ではA上でそれぞれの端子対を結び,長さの総和が最小な非交差直交道を求める効率の良いアルゴリズムを与えた.平面グラフ上の問題に帰着させて問題を解いており,アルゴリズムの計算時間はO(nlogn)である.ここでn=r+kである.このアルゴリズムはVLSIの一層配線問題等に応用できる.3.平面領域にm個の長方形障害物とn個の2層配線領域が与えられているとする.障害物の内部でない4点a,a´,b,b´が与えられたときに,a,a´とb,b´を結ぶ2本の道で2層配線領域以外では交差しないものの内で長さの和が最小なものを求めるアルゴリズムを与えた.計算時間はO((m+n)log(m+n))である.このアルゴリズムもVLSIの配線問題等に応用を持ち有用である.

The problem on the top of the list is solved effectively and the problem on the top of the list is solved gradually. The main results are as follows: 1. The linear time solution of the linear time problem of the straight parallel problem of the partial k-tree is the linear time solution of the color problem of the straight parallel problem of the multiple parallel problem of the partial k-tree is the linear time solution of the polynomial time problem of the partial k-tree. In this study, the number of color lines in the vertical parallel multiple lines was calculated.| V| log| E| The time is specific, the color is sought, the sequence is lost, the color is lost, and the color is lost. O(log)| V| The time limit is set for the first time.ここでVとEはそれぞれ与えられる直并列多重グラフの点集合と辺集合である. The result is useful for solving the problem. 2. The outer rectangle and the inner rectangle (inner rectangle) are the planar domain. A and the inner rectangle are the rectangular obstacles. The outer rectangle and the inner rectangle have k groups of terminal pairs assigned to them. In this study, the terminal pairs on the A side are connected to each other, and the total sum of the terminals is reduced to the minimum. The time required to solve the problem is O(nlogn).ここでn=r+kである. 3. m rectangular barriers in the planar domain and n two-layer wiring domains. The interior of the barrier is divided into 4 points a,a ′,b,b ′ and a,a ′, b ′. The junction is less than 2 layers. The intersection is outside the 2-layer wiring field. The intersection is different. The interior is long. The sum is the smallest. Calculation time O((m+n)log(m+n)). The problem of wiring in VLSI is that it is necessary to maintain all the useful information.