ネットワーク最適化問題の解法効率化に関する研究
ネットワーク最適化問題の解法効率化に関する研究
批准号:
10205219
负责人:
WATANABE Toshimasa
金额:
$6.59万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份:
1998
资助国家:
日本
项目状态:
已结题
起止时间:
1998 至 2000
中文摘要
目的:研究设计网络优化问题的最优解或尖锐近似解的有效算法。研究结果:分为以下几类。(1)构建可生存网络:提出了寻找连通性增强问题最优解或近似解的算法,其中将链路或节点故障幸存的网络设计建模为连通性增强问题。考虑了以下问题。(i)不创建图的多条边的k边连通性增强问题;(ii)边多重性有上界的k边连通性增强问题;(iii) k边连通性增强问题的分布式算法;(iv)超图的Steiner树问题的逼近算法。(2)通信协议设计与验证的基础研究:提出了获取虹吸管或Petri网不变量的有效算法,其中通信协议的验证或周期性分别与建模中使用的虹吸管或不变量或Petri网密切相关。考虑了以下问题。(i)抽取最少的虹吸;最小支持不变量的计算。(3)求解调度问题:将调度问题建模为在普通Petri网或定时Petri网中寻找合法的发射序列,并提出了有效的启发式算法。(4)印制板设计:针对印制板设计中的几个基本问题,提出了高效的启发式算法。考虑了以下问题。(i)提取生成平面子图;路线问题;受到最小化问题的限制。(5)图形绘制:提出了在给定曲面上绘制图形的高效算法,该算法满足了绘制图形的许多实际约束,如最小化总长度或直线的交叉点,指定某些直线的交叉点等。(6)其他:出版了关于算法设计与分析的《数据结构与基本算法》一书,用大量的图形对基本概念进行了详细的解释。少
英文摘要
Purposes : Research on designing efficient algorithms for finding optimum solutions or sharp approximate ones to the network optimization problems.Research results : They are divided into the following categories.(1) Constructing survivable networks : Algorithms for finding optimum or approximate solutions to the connectivity augmentation problems are proposed, where designing networks that survive link or node faults is modeled as the connectivity augmentation problems. The following problems are considered. (i) K-edge-connectivity augmentation problems without creating multiple edges of a graph; (ii) K-edge-connectivity augmentation problems with upper bounds on edge multiplicity; (iii) Distributed algorithms for the k-edge-connectivity augmentation problems; (iv) Approximation algorithms for the Steiner tree problem of hypergraphs.(2) Fundamental research on design and verification of communication protocols : Efficient algorithms for obtaining siphons or invariants of Petri nets ar … More e proposed, where verification or periodicity of communication protocols, respectively, is closely related to siphons or invariants or Petri nets that are used in modeling. The following problems are considered. (i) Extraction of minimal siphons; (ii) Computation of minimal support invariants.(3) Solving scheduling problems : Scheduling problems are modeled as finding legal firing sequences in ordinary or timed Petri nets, and efficient heuristic algorithms are proposed.(4) Designing printed wiring boards : Efficient heuristic algorithms for several fundamental problems in designing printed wiring boards are proposed. The following problems are considered. (i) Extracting spanning planar subgraphs; (ii) Routing problems; (iii) Constrained via minimization problems.(5) Graph drawing : Efficient algorithms for drawing graphs on a given surface are proposed, where many practical constraints on graph drawing, such as minimizing total length or crossing of lines, specifying crossing points of certain lines, and so on, are satisfied.(6) Others : A book entitled "Data Structures and Fundamental Algorithms" on design and analysis of algorithms is published, where basic concepts are explained in great detail by using many figures. Less
期刊论文(94)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Takahashi, K., Watanabe, T.: "A Heuristic Algorithm to Solve Constrained via Minimization Three-Layer Routing Problems"Proc.1998 IEEE International Symposium on Circuits and Systems. Vol.6. VI254-VI257 (1998)
Takahashi, K.,Watanabe, T.:“通过最小化解决受约束的三层路由问题的启发式算法”Proc.1998 IEEE 国际电路与系统研讨会。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Fujito, T., Taoka, S., Watanabe, T.: "On the Legal Firing Sequence Problem of Petri Nets with Cactus Structure"IEICE Trans.Fundamentals. Vol.E83-A,No.3. 480-486 (2000)
Fujito, T.、Taoka, S.、Watanabe, T.:“仙人掌结构 Petri 网的合法发射序列问题”IEICE Trans.Fundamentals。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Nishi, S., Taoka, S., Watanabe, T.: "A Heuristic Algorithm FMD for the Minimum Initial Marking Problem of Petri Nets"Proc.13th Karuizawa Workshop on Circuits and Systems,IEICE of Japan. 275-280 (2000)
Nishi, S.、Taoka, S.、Watanabe, T.:“Petri 网最小初始标记问题的启发式算法 FMD”Proc.第 13 届轻井泽电路与系统研讨会,日本 IEICE。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
高藤 大介, 伊藤 貴史, 田岡 智志, 渡邉 敏正: "CONTEC: 辺交差の制御機能を有するグラフ描画システム"信学技報,COMP99-76. 57-64 (2000)
Daisuke Takato、Takashi Ito、Satoshi Taika、Toshimasa Watanabe:“CONTEC:具有边缘交叉控制功能的图形绘制系统”IEICE 技术报告,COMP99-76 (2000)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Mashima, T., Watanabe, T.: "Solving the 2-,3-vertex-connectivity augmentation problem for specified vertices of a graph with degree-unchangeable ones"Tech.Rep.of IEICE,COMP99-77. 65-72 (2000)
Mashima, T.,Watanabe, T.:“解决具有度数不可改变的图的指定顶点的 2-,3-顶点连通性增强问题”Tech.Rep.of IEICE,COMP99-77。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 94 条
Integrated Research on Connectivity of Graphs and its Applications
-
批准号:20500015
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.91万
-
财政年份:2008
-
负责人:WATANABE Toshimasa
-
依托单位:
Integrated Research on Connectivity of Graphs
-
批准号:18500014
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.55万
-
财政年份:2006
-
负责人:WATANABE Toshimasa
-
依托单位:
A study on Connectivity of Graphs and Its Applications
-
批准号:15500011
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.43万
-
财政年份:2003
-
负责人:WATANABE Toshimasa
-
依托单位: