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

用途：研究设计有效的算法，以寻找网络优化问题的最优解或精确近似解。研究成果：它们分为以下几类。(1)构建可生存的网络：提出了寻找连接性增强问题的最佳或近似解决方案的算法，其中设计能够在链路或节点故障下生存的网络被建模为连接性增强问题。考虑以下问题。(i)K-边连通性扩充问题，而不创建多个边的图;（ii）K-边连通性扩充问题与上界的边缘多重性;（iii）分布式算法的k-边连通性扩充问题;（iv）近似算法的斯坦纳树问题的超图。(2)通信协议设计和验证的基础研究：获得Petri网信标或不变量的有效算法， 关于我们 e提出，其中验证或通信协议的周期性，分别是密切相关的信标或不变量或Petri网中使用的建模。考虑以下问题。(i)最小信标的提取;（ii）最小支持不变量的计算。(3)解决调度问题：调度问题被建模为在普通Petri网或赋时Petri网中寻找法律的点火序列，并提出了有效的启发式算法。(4)设计印刷线路板：提出了设计印刷线路板中几个基本问题的有效启发式算法。考虑以下问题。(i)提取生成平面子图;（ii）布线问题;（iii）约束通过最小化问题。(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