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

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

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.