Complexity of Partition Problems

分区问题的复杂性

基本信息

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

项目摘要

This proposal concerns several problem areas within the common theme of algorithmic graph theory. While many standard algorithmic and optimization problems are intractable (that is, NP-complete) in general, efficient algorithms become possible if the inputs are restricted to certain natural and well-structured networks (that is, graphs and digraphs). This is in particular true for many graph colouring problems and their generalizations and variants studied in this research. One of the objectives will be to illuminate the kind of structure that is helpful for such problems, and identify such situations. Sometimes this involves proving intractability (NP-completeness) of the problems investigated, at other times it involves designing algorithms that take advantage of the special structure these networks posses. This may take various forms, from using a geometric representation of the input, to using its recursive description, or other characterization. While this has been well explored in the case of undirected graphs, the novelty of our approach will be to systematically widen the focus to directed graphs. Surprisingly, it appears that with small exceptions the analogies are not sufficiently well explored, and we have already observed in recent investigations that interesting novel phenomena can and do arise. The focus on general digraphs is a significant extension of the current theory and applications of undirected graph classes (and their corresponding specialized algorithms), which is quite established and very successful. Our main focus will be on partition problems, typified (in the undirected case) by such classical concepts as graph colouring, graph homomorphisms, and matrix partitions. The structures investigated will be defined by the existence of special ordering, or the existence of special orientations, or the existence of novel geometric representations. In addition, we will examine the power of such descriptions, and study which digraph classes can be described by such characterizations.
这一建议涉及算法图论的共同主题中的几个问题领域。虽然许多标准的算法和优化问题通常是棘手的(即NP完全的),但如果输入限于某些自然的和结构良好的网络(即图和有向图),则高效的算法是可能的。对于本研究中研究的许多图着色问题及其推广和变体,情况尤其如此。目标之一将是阐明有助于解决此类问题的结构类型,并确定此类情况。这有时涉及证明所研究问题的难解性(NP-完备性),有时涉及设计利用这些网络所具有的特殊结构的算法。这可以采取各种形式,从使用输入的几何表示,到使用其递归描述或其他表征。虽然在无向图的情况下已经很好地探索了这一点,但我们方法的新颖性将是系统地将重点扩大到有向图。令人惊讶的是,除了一些小的例外,这些类比似乎没有得到充分的探索,我们已经在最近的调查中观察到,有趣的新奇现象可以而且确实会出现。对一般有向图的研究是对当前无向图类的理论和应用(及其相应的专门算法)的一个重要扩展,这是非常成熟和非常成功的。我们的主要焦点将集中在划分问题上,由图着色、图同态和矩阵划分等经典概念来表示(在无向情况下)。所研究的结构将由特殊有序的存在,或特殊取向的存在,或新的几何表示的存在来定义。此外,我们还将考察这种刻画的能力,并研究哪些有向图类可以用这种刻画来刻画。

项目成果

期刊论文数量(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 }}

Hell, Pavol其他文献

Min-Orderable Digraphs
最小可排序有向图
  • DOI:
    10.1137/19m1241763
  • 发表时间:
    2020
  • 期刊:
  • 影响因子:
    0.8
  • 作者:
    Hell, Pavol;Huang, Jing;McConnell, Ross M.;Rafiey, Arash
  • 通讯作者:
    Rafiey, Arash
Complexity of coloring graphs without paths and cycles
  • DOI:
    10.1016/j.dam.2015.10.024
  • 发表时间:
    2017-01-10
  • 期刊:
  • 影响因子:
    1.1
  • 作者:
    Hell, Pavol;Huang, Shenwei
  • 通讯作者:
    Huang, Shenwei
On the adaptable chromatic number of graphs
  • DOI:
    10.1016/j.ejc.2007.11.015
  • 发表时间:
    2008-05-01
  • 期刊:
  • 影响因子:
    1
  • 作者:
    Hell, Pavol;Zhu, Xuding
  • 通讯作者:
    Zhu, Xuding
Colouring, constraint satisfaction, and complexity
  • DOI:
    10.1016/j.cosrev.2008.10.003
  • 发表时间:
    2008-12-01
  • 期刊:
  • 影响因子:
    12.9
  • 作者:
    Hell, Pavol;Nesetril, Jaroslav
  • 通讯作者:
    Nesetril, Jaroslav
Oriented star packings
  • DOI:
    10.1016/j.jctb.2007.09.004
  • 发表时间:
    2008-05-01
  • 期刊:
  • 影响因子:
    1.4
  • 作者:
    Brewster, Richard C.;Hell, Pavol;Rizzi, Romeo
  • 通讯作者:
    Rizzi, Romeo

Hell, Pavol的其他文献

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

{{ truncateString('Hell, Pavol', 18)}}的其他基金

Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2019-04221
  • 财政年份:
    2021
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2019-04221
  • 财政年份:
    2020
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2019-04221
  • 财政年份:
    2019
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2018
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2017
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2016
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2015
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2014
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Load disaggregation
负载分解
  • 批准号:
    463771-2014
  • 财政年份:
    2014
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Engage Plus Grants Program
Complexity of partition problems
分区问题的复杂性
  • 批准号:
    5075-2009
  • 财政年份:
    2013
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual

相似海外基金

Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2019-04221
  • 财政年份:
    2021
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2019-04221
  • 财政年份:
    2020
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2019-04221
  • 财政年份:
    2019
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2018
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2017
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2016
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2015
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of Partition Problems
分区问题的复杂性
  • 批准号:
    RGPIN-2014-05508
  • 财政年份:
    2014
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of partition problems
分区问题的复杂性
  • 批准号:
    5075-2009
  • 财政年份:
    2013
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
Complexity of partition problems
分区问题的复杂性
  • 批准号:
    5075-2009
  • 财政年份:
    2012
  • 资助金额:
    $ 4.01万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了