TSP in Combinatorial Optimization and CSP in Theoretical Computer Science

组合优化中的 TSP 和理论计算机科学中的 CSP

• 批准号: 18F18746
• 负责人: 河原林 健一
• 金额: $ 0.9万
• 依托单位: National Institute of Informatics
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-11-09 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18F18746/
• 关键词: グラフ; グラフ彩色; 組合せ最適; graph; TSP; matroid; CSP

本研究では、離散数学、組合せ最適化、グラフアルゴリズムにおける中心的研究課題である「グラフ彩色問題」と「グラフカット問題」に対して、最先端の研究課題の改良を試み、部分的な結果を得た。さらに、グラフ彩色問題とグラフカット問題の拡張概念であるCSP 問題、VCSP 問題に対して、多くの知見を得た。受け入れ研究者は、グラフ３彩色問題、グラフカット問題にて、現在の最先端の結果を得ており、特別研究員は、CSP とVCSP 問題の専門家である。本共同研究では、両方の専門性を組み合わせて、多くの知見を得た。

The research topics of this study, scattered mathematics, integrated optimization, and the research center of the center of research, such as the color problem, the color problem, the problem, the research problem, the improvement problem, and some of the results have been obtained. The concept of the CSP problem, the VCSP problem, the knowledge of the multi-user, and the knowledge of each other. I have been invited to join the researcher, received 3 color questions, received a few questions, and are now the first to get results, special research staff, and CSP VCSP questions. The purpose of this study is to make a joint study on the combination of sexual organization and knowledge in this study.

项目成果

Surjective valued constraint satisfaction problem

满值约束满足问题

• 发表时间: 2019
• 作者: Fulla Peter;Uppman Hannes;Zivny Stanislav;Peter Fulla
• 通讯作者: Peter Fulla

The Complexity of Boolean Surjective General-Valued CSPs

布尔满射通用值 CSP 的复杂性

• DOI: 10.1145/3282429
• 发表时间: 2018
• 期刊: ACM Transactions on Computation Theory
• 影响因子: 0.7
• 作者: Fulla Peter;Uppman Hannes;Zivny Stanislav
• 通讯作者: Zivny Stanislav