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

Discrete Optimization Problems with Graph and Network Structures and Their Efficient Solution Methods

图和网络结构的离散优化问题及其高效求解方法

基本信息

批准号：
10205210
负责人：
MASUYAMA Shigeru
金额：
$ 6.98万
依托单位：
Toyohashi University of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas (B)
财政年份：
1998
资助国家：
日本
起止时间：
1998 至 2000
项目状态：
已结题

项目摘要

A number of problems which have emerged due to the recent rapid progress of Internet, multimedia networks, mobile and wireless networks and computer technology have a discrete structure in nature. Thus we first formalize some of such problems as graph and/or network problems and tried to obtain efficient solution methods by elucidating their structural feature. As a result, efficient algorithms, either parallel or sequential, for Hamiltonian circuit problem on an in-tournament graph, two edge-disjoint paths problem on tournament graph, hinge vertex problem in an interval graph and a trapezoid graph were obtained in the field of network reliability. Moreover, some results on location problems of servers and mirrors on multimedia networks and area assignment to base stations in mobile and wireless networks are also obtained. In discrete geometry, generalization of the 2-dimension ham sandwich problem which was an open problem was solved and NP-completeness of stage illumination problem was also clarified. On discrete games and puzzles, NP-hardness of rotation type cell-mazes and PSPACE-completeness of generarized Tsume-Shogi with a given number of moves were proved. Hardware accelerator for subgraph isomorphism problem was developed and static load balancing of parallel PDE solver for distributed computing environment is also investigated. As technologies for supporting users to utilize a large amount of information now available via Internet, etc, some results on automatic text summarization, a retrieval method for relevant documents and knowledge-acquisition from corpus were also obtained.

由于最近互联网、多媒体网络、移动和无线网络以及计算机技术的快速发展而出现的一些问题，本质上是一个离散的结构。因此，我们首先将图和/或网络问题等问题形式化，并试图通过阐明它们的结构特征来获得有效的求解方法。结果，在网络可靠性领域，得到了关于竞赛图上的哈密顿回路问题、竞赛图上的两条边不相交的路问题、区间图上的铰链顶点问题和梯形图的有效的并行或顺序算法。此外，还得到了多媒体网络中服务器和镜像的位置问题以及移动和无线网络中基站的区域分配问题的一些结果。在离散几何中，解决了二维火腿三明治问题这一公开问题的泛化问题，并阐明了舞台照明问题的NP完备性。在离散对策和谜题上，证明了旋转型细胞迷宫的NP-硬度和给定步数的广义Tsum-Shogi的空间完备性。开发了子图同构问题的硬件加速器，研究了分布式计算环境下并行PDE求解器的静态负载均衡问题。作为支持用户利用现有互联网上的大量信息的技术等，在自动文本摘要、相关文档的检索方法和从语料库中获取知识等方面也取得了一些成果。