Graph Algorithms

图算法

基本信息

  • 批准号:
    RGPIN-2016-06517
  • 负责人:
  • 金额:
    $ 2.26万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2019
  • 资助国家:
    加拿大
  • 起止时间:
    2019-01-01 至 2020-12-31
  • 项目状态:
    已结题

项目摘要

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.****Many theorems in mathematics state that the number of something is even (or odd). Usually they are proved by counting arguments. We use a different approach: we construct an “exchange graph”, where the “odd-degree” vertices correspond to the objects we want to show there is an even number of. Besides often providing a simpler proof, an exchange graph provides an algorithm for the problem: Given one object, find another. Since the number of objects is even, we know a second one exists. We are studying the efficiency of such algorithms, in particular for theorems concerning trees and cycles in graphs.****Much of my research focuses on finding efficient algorithms for optimization problems on graphs such as minimum colouring and largest stable set. These problems have many applications including scheduling and in molecular biology. They are NP-hard for arbitrary graphs, which means that it is unlikely that efficient algorithms exist to solve them in general. However, graphs arising in applications often have special structure, which can sometimes be exploited to design efficient algorithms. I study specially structured graphs, where certain subgraphs are excluded or graphs with a nice intersection model. I try to discover properties of graphs in certain classes, to understand which properties are useful for solving which problems, and then use these properties to design efficient algorithms. ****Optimum matching is a well-solved problem with many applications including kidney exchange. Matchings in a graph correspond precisely to stable sets in its “line-graph”. Line-graphs are a subclass of “claw-free graphs” which are a subclass of “pan-free graphs”, and thus the stable set problem in either of these two specially-structured classes generalizes the matching problem. (A pan is a chordless cycle with at least four vertices together with a pendant edge.) Minty's (1980) efficient algorithm for maximum weight stable set in claw-free graphs led to much research on claw-free graphs, including the generalization of it by Brandstadt, Lozin and Mosca (2010) to pan-free graphs. Quite anomalously, these did not provide a defining system for the corresponding “stable set polytope”. Much ongoing work focuses on finding a defining system for claw-free graphs. I am studying the structure and the stable set polytope of subclasses of pan-free graphs.********
我研究的一个主要方向是寻找一些定理,这些定理表明容易识别的东西总是存在的,然后试图找到有效地存在的东西。“易识别”和“高效”的概念在计算理论中被形式化为“在NP中”和“多项式时间”。非正式地,这个研究方向可以表述为:如果它很容易识别,而且你知道它在那里,那么它肯定不难找到。(任何把钥匙放错地方的人可能都不会同意!)这让我找到了一些有效的算法来解决之前没有考虑过的不相关问题。****许多数学定理都指出某数是偶数(或奇数)。通常它们是通过计数论证来证明的。我们使用一种不同的方法:我们构建一个“交换图”,其中“奇度”顶点对应于我们想要显示的对象的偶数个。交换图除了通常提供更简单的证明之外,还提供了解决问题的算法:给定一个对象,找到另一个对象。由于物体的数量是偶数,我们知道存在第二个物体。我们正在研究这些算法的效率,特别是关于图中的树和循环的定理。****我的大部分研究都集中在寻找有效的算法来解决图上的优化问题,如最小着色和最大稳定集。这些问题有许多应用,包括调度和分子生物学。它们对于任意图来说都是np困难的,这意味着不太可能存在有效的算法来解决它们。然而,应用程序中出现的图形通常具有特殊的结构,有时可以利用它来设计高效的算法。我研究特殊结构的图,其中某些子图被排除在外或具有良好相交模型的图。我试图在某些类中发现图的属性,了解哪些属性对解决哪些问题有用,然后利用这些属性来设计高效的算法。****最佳匹配是一个很好的解决了许多应用的问题,包括肾脏交换。图中的匹配精确地对应于其“线形图”中的稳定集。线形图是“无爪图”的一个子类,而“无盘图”又是“无爪图”的一个子类,因此这两个特殊结构类中的稳定集问题推广了匹配问题。(平底锅是一个无弦循环,至少有四个顶点和一个垂边。)Minty(1980)关于无爪图中最大权稳定集的高效算法引起了对无爪图的大量研究,包括Brandstadt, Lozin和Mosca(2010)将其推广到pan-free图。非常反常的是,这些并没有为相应的“稳定集多面体”提供一个定义系统。许多正在进行的工作集中在寻找无爪图的定义系统。我正在研究无盘图子类的结构和稳定集多面体。********

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Cameron, Kathleen其他文献

Dissemination and implementation of evidence-based programs for people with chronic disease: the impact of the COVID-19 pandemic.
  • DOI:
    10.3389/fpubh.2023.1276387
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    5.2
  • 作者:
    Coyle, Peter;Tripken, Jennifer;Perera, Subashan;Juarez, Gardenia A.;Spencer-Brown, Lesha;Cameron, Kathleen;Brach, Jennifer S.
  • 通讯作者:
    Brach, Jennifer S.

Cameron, Kathleen的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Cameron, Kathleen', 18)}}的其他基金

Graph Algorithms
图算法
  • 批准号:
    RGPIN-2016-06517
  • 财政年份:
    2022
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Algorithms
图算法
  • 批准号:
    RGPIN-2016-06517
  • 财政年份:
    2021
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Algorithms
图算法
  • 批准号:
    RGPIN-2016-06517
  • 财政年份:
    2020
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Algorithms
图算法
  • 批准号:
    RGPIN-2016-06517
  • 财政年份:
    2018
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Algorithms
图算法
  • 批准号:
    RGPIN-2016-06517
  • 财政年份:
    2017
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Algorithms
图算法
  • 批准号:
    RGPIN-2016-06517
  • 财政年份:
    2016
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph algorithms
图算法
  • 批准号:
    122793-2009
  • 财政年份:
    2014
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph algorithms
图算法
  • 批准号:
    122793-2009
  • 财政年份:
    2012
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph algorithms
图算法
  • 批准号:
    122793-2009
  • 财政年份:
    2011
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual
Graph algorithms
图算法
  • 批准号:
    122793-2009
  • 财政年份:
    2010
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Discovery Grants Program - Individual

相似海外基金

CAREER: Fast Scalable Graph Algorithms
职业:快速可扩展图算法
  • 批准号:
    2340048
  • 财政年份:
    2024
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
  • 批准号:
    2347322
  • 财政年份:
    2024
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
  • 批准号:
    2347321
  • 财政年份:
    2024
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Standard Grant
CAREER: Theory for Dynamic Graph Algorithms
职业:动态图算法理论
  • 批准号:
    2238138
  • 财政年份:
    2023
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Continuing Grant
Collaborative Research: ATD: Fast Algorithms and Novel Continuous-depth Graph Neural Networks for Threat Detection
合作研究:ATD:用于威胁检测的快速算法和新颖的连续深度图神经网络
  • 批准号:
    2219956
  • 财政年份:
    2023
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Standard Grant
Communication Complexity of Graph Algorithms (GraphCom)
图算法的通信复杂性(GraphCom)
  • 批准号:
    EP/X03805X/1
  • 财政年份:
    2023
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Research Grant
Collaborative Research: SaTC: CORE: Medium: Graph Mining and Network Science with Differential Privacy: Efficient Algorithms and Fundamental Limits
协作研究:SaTC:核心:媒介:具有差异隐私的图挖掘和网络科学:高效算法和基本限制
  • 批准号:
    2317192
  • 财政年份:
    2023
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Continuing Grant
Collaborative Research: SaTC: CORE: Medium: Graph Mining and Network Science with Differential Privacy: Efficient Algorithms and Fundamental Limits
协作研究:SaTC:核心:媒介:具有差异隐私的图挖掘和网络科学:高效算法和基本限制
  • 批准号:
    2317194
  • 财政年份:
    2023
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Continuing Grant
AF: Small: Algorithms for Graph Cuts
AF:小:图割算法
  • 批准号:
    2329230
  • 财政年份:
    2023
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Standard Grant
Ambue scaling retrofit with graph algorithms
使用图算法进行 Ambue 缩放改造
  • 批准号:
    10066194
  • 财政年份:
    2023
  • 资助金额:
    $ 2.26万
  • 项目类别:
    Collaborative R&D
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了