Graph Algorithms

图算法

• 批准号: RGPIN-2016-06517
• 负责人: Cameron, Kathleen
• 金额: $ 2.26万
• 依托单位: Wilfrid Laurier University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634937
• 关键词: Graph; Algorithms

A main direction of my research is to look for theorems which say that something that is easy to recognize always exists, and then to try to find what exists efficiently. The concepts “easy to recognize” and “efficiently” are formalized in computing theory as “in NP” and “polynomial time”. Informally this research direction can be stated as: if it’s easy to recognize and you know it’s there, surely it’s not hard to find. (Anyone who has misplaced their keys at home may not agree!) This has led me to find efficient algorithms for unrelated problems I might not have considered before.

我的研究的一个主要方向是寻找定理，说什么是容易识别的总是存在的，然后试图找到什么存在有效。“容易识别”和“有效”的概念在计算理论中被形式化为“在NP中”和“多项式时间”。非正式地说，这一研究方向可以表述为：如果它很容易识别，你知道它在那里，那么它肯定不难找到。（任何在家里放错钥匙的人都可能不同意！）这使我找到了解决以前可能没有考虑过的不相关问题的有效算法。