Advances in Theory and Design Principles of Counting AlgorithmsBased on Polyhedral Combinatorics

基于多面体组合的计数算法理论与设计原理研究进展

• 批准号: 21700009
• 负责人: OKAMOTO Yoshio
• 金额: $ 2.66万
• 依托单位: The University of Electro-Communications (2011)Japan Advanced Institute of Science and Technology (2010)Tokyo Institute of Technology (2009)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21700009/
• 关键词: アルゴリズム; 離散数学; 凸多面体; グラフ; 離散幾何

Results on counting problems for graphs, counting problems for discrete and computational geometry, and their applications to optimization problems were obtained. For example, the computational complexity of counting the dominating sets in a graph was investigated from the perspective of graph classes, and a polynomial-time algorithm to find a global optimal solution to the distance function maximization was developed by efficiently enumerating all local optimal solutions. These results were presented in refereed international journals and refereed international conferences.

结果计算图形问题，计算离散和计算几何形状的问题以及它们在优化问题上的应用。例如，从图形类别的角度研究了计算图中主导集的计算复杂性，并通过有效列举所有本地最佳解决方案来开发出多项式时间算法以找到对距离函数最大化的全局最佳解决方案。这些结果是在审查的国际期刊和审计国际会议上提出的。

项目成果

Submodular fractional programming for balanced clustering

• DOI: 10.1016/j.patrec.2010.08.008
• 发表时间: 2011
• 期刊: Pattern Recognit. Lett.
• 作者: Y. Kawahara;Kiyohito Nagano;Y. Okamoto

グラフを通したパズル・ゲームの一般化

通过图表概括益智游戏

• 发表时间: 2013
• 期刊: オペレーションズ・リサーチ
• 作者: Yota Otachi;Toshiki Saitoh;Katsuhisa Yamanaka;Shuji Kijima;Yoshio Okamoto;Hirotaka Ono;Yushi Uno;and Koichi Yamazaki;岡本 吉央
• 通讯作者: 岡本 吉央

コア安定性の計算理論

核心稳定性计算理论

• 作者: M.Villagra;M.Nakanishi;S.Yamashita;Y.Nakashima;岡本 吉央
• 通讯作者: 岡本 吉央

離散体積計算による組合せ数学入門

使用离散体积计算介绍组合数学

• 发表时间: 2010
• 作者: M.ベック;S.ロビンス(岡本吉央訳)
• 通讯作者: S.ロビンス(岡本吉央訳)

Counting the number of matchings in chordal and chordal bipartite graphs

计算弦图和弦二部图中的匹配数

• 发表时间: 2010
• 期刊: Lecture Notes in Computer Science
• 作者: Yoshio Okamoto;Ryuhei Uehara;Takeaki Uno
• 通讯作者: Takeaki Uno