Algorithmic approaches to hard geometric and graph theoretic problems

困难几何和图论问题的算法方法

• 批准号: 259-2009
• 负责人: Keil, Mark
• 金额: $ 1.38万
• 依托单位: University of Saskatchewan
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=449071
• 关键词: Algorithmic; approaches; hard; geometric; graph

Constructing and manipulating a computational model is central in many computer science applications. Unfortunately, often the problems that naturally arise turn out to be hard, in the sense that the best known algorithms cannot find exact solutions in a reasonable amount of time. Computational models involving graphs are pervasive in applications, and where physical objects are modeled, geometric models are important. The objective of this research program is to develop effective algorithmic approaches to some natural hard geometric and graph theoretic problems. The approaches will include the development of algorithms that yield approximate solutions as well as algorithms that yield exact solutions but only to restricted instances of the problems.

构造和操纵计算模型是许多计算机科学应用的核心。不幸的是，自然产生的问题往往很难解决，因为最知名的算法无法在合理的时间内找到精确的解决方案。涉及图的计算模型在应用中是普遍存在的，并且在对物理对象建模的情况下，几何模型是重要的。本研究计划的目标是发展有效的算法方法，一些自然的硬几何和图论问题。这些方法将包括开发产生近似解的算法以及产生精确解的算法，但仅限于问题的有限实例。