ネットワーク最適化問題の解法効率化に関する研究

提高网络优化问题求解效率的研究

• 批准号: 10205219
• 负责人: WATANABE Toshimasa
• 金额: $ 6.59万
• 依托单位: Hiroshima University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205219/
• 关键词: Network optimization problem; Survivable networks; Petri net invariants; Timed Petri net scheduling; Printed wiring board design; Graph drawing; Design and Analysis of algorithms; Distributed algorithms; アルゴリズム設計; 計算複雑度; 解法の効率化; 近似解法; 近似解の精度 /

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

目的：研究设计寻找网络优化问题最优解或尖锐近似解的算法。研究成果：分为以下几类。（1）构建可生存网络：寻找连通性最优有效或近似近似解的算法提出了增强问题，其中将设计能够承受链路或节点故障的网络建模为连接增强问题，并考虑以下问题（i）不创建图的多个边的 K 边连接增强问题；具有边重数上限的 K 边连通性增广问题；(iii) k 边连通性增广问题的分布式算法；(iv) 超图 Steiner 树问题的逼近算法。通信协议的验证：提出了用于获得虹吸管或 Petri 网不变量的有效算法，其中通信协议的验证或周期性分别与建模中使用的虹吸管或不变量或 Petri 网考虑以下问题（i）最小虹吸管的提取；（ii）最小支持不变量的计算。（3）解决调度问题：将调度问题建模为寻找合法的触发。普通或定时Petri网中的序列，并提出了有效的启发式算法。(4)设计印刷线路板：针对设计印刷线路板中的几个基本问​​题提出了有效的启发式算法。 (i) 提取跨越平面子图；(ii) 路由问题；(iii) 通过最小化问题进行约束。(5) 图绘制：提出了在给定表面上绘制图的有效算法，其中对图绘制有许多实际约束，例如满足最小化总长度或线的交叉点，指定某些线的交叉点等。（6）其他：一本关于算法设计和分析的书“数据结构和基本算法”已发表，其中使用许多图表详细解释了基本概念。