双向グラフに対する最適化問題とその解法の研究

双向图优化问题及其求解研究

基本信息

批准号：
09740135
负责人：
田村明久
金额：
$ 1.28万
依托单位：
The University of Electro-Communications
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

项目摘要

「双向グラフに対する最適化問題とその解法の研究」という目的で昨年度に引き続き本年度は研究を進めて来た。昨年度の研究成果“The generalized stable set problem for claw-free bidirected graphs"について、1998年の6月に開催された国際会議Integer Programming and Combinatorial Optimization(査読付き)にて口頭発表を行った。その際の旅費として本年度の研究費を用いた。また本論文はこの会議のプロシーディングスに掲載された。本年度の研究成果は“A linear time algorthm for the generalized stable set problem on triangulated bidirected graphs"としてまとめ、Journal of the Operations Research Society of Japanに投稿し、1999年3月17〜19日に京都大学で開催されるJapan-Hungarian Symposium on Discrete Mathematics and Its Applicationsにて口頭発表する。また、この成果については来年度開催される国内外の学術会議、研究会においても口頭発表を行う予定である。この成果は本年度計画していた「一般の双向グラフについて一般化安定集合問題に対する効率的な解放の開発」を含むものである。もう一つの計画「平面上の与えられた点集合の最小重み三角形分割問題へのこの解法の応用」については現在研究中でありまだ成果を得るに至っていない。また開発した解法については、当研究費によって購入した計算機を用いてその実用面での有効性の検証も行った。

在去年之后，我们继续进行研究，目的是“研究双向图及其解决方案的优化问题”。关于去年的研究发现，在1998年6月举行的国际会议，整数编程和组合优化（PEER-RIEFTIED）上，就去年的研究结果进行了口头介绍。今年的研究资金被用作旅行费用。本文也发表在本次会议论文集中。今年的研究结果将被汇编为“在三角分配的图表上的普遍稳定设置问题的线性时间算法”，并发表在《日本运营研究学会杂志》杂志上，并在日本 - 亨加利亚研讨会上进行了口头介绍，该组织将在离散的数学及其应用程序上在Kyoto Universition上进行，从3月17日进行了研究。国际学术会议和研究小组将于明年举行。该结果包括“今年计划的通用双向图的广义稳定集问题的有效释放”。另一个计划是“将这种解决方案应用于飞机上给定的一组点的最小重量三角剖分问题”，目前正在研究中，尚未实现。还使用研究基金购买的计算机验证了开发解决方案的实际有效性。