图的染色和控制集问题的理论和算法研究

结题报告
项目介绍
AI项目解读

基本信息

  • 批准号：
    10971248
  • 项目类别：
    面上项目
  • 资助金额：
    25.0万
  • 负责人：
    吕长虹
  • 依托单位：
    华东师范大学
  • 学科分类：
    A0409.图论及其应用
  • 结题年份：
    2012
  • 批准年份：
    2009
  • 项目状态：
    已结题
  • 起止时间：
    2010-01-01 至2012-12-31

项目摘要

图染色一直是图论研究的主流问题，在理论和应用方面均有其积极意义。图的控制集问题及其各种推广形式是目前图论研究发展最快的领域之一。图的染色和控制集问题均与图的结构具有密切联系,其研究主要涉及到组合图论方法,随机方法,代数方法,线性规划以及由此产生的各种算法。本项目主要考虑各种形式的染色问题和控制集问题的性质和算法。主要内容有：一，围绕 M.Karonski等人在 2004年提出的猜想,对一般图或特殊图类vertex-coloring edge-weightings及相关问题的参数进行估计,包括极图的刻画等；二，采用组合手段,代数和随机方法,结合新的first-fit思想，对L(j,k)-labling等问题提供一些新的技术和想法；三，考虑chordal graphs及其子图类上各种控制集问题的有效算法。

结项摘要

图的距离标号问题是图的经典染色问题的推广，也与频率分配问题有关。本项目研究图的L(2,1)-标号数和路覆盖数。我们给出了树和树状图路覆盖数的许多结果，给出了线性时间算法发现树满足其补图具有唯一island sequence。我们的工作推广了S.S. Adams等人2010年的主要工作，同时回答了J.P. Georges和 D.W. Mauro 2005年提出的公开问题。.控制集问题是运筹学中选址问题的自然模型。由于各种应用的需要，各种各样的控制集问题被人们研究。本项目考虑r-locating-domination set, r-identifying code, paired-domination, restrained domination等问题..（1）对r-identifying codes问题， D.L. Roberts 和 F.S. Roberts 在2008年(见[5])给出了r = 2时路和圈的完整结果。我们对一般的正整数r给出了完整结果。对于2-locating- dominating sets 问题，N. Bertrand 等人在2004年(见[6])给出部分结果,我们同样给出完整结果。.（2）对block graphs和interval graphs的paired -domination problem进行研究，给出其线性时间算法,同时我们证明了split graphs的paired -domination problem是NP-complete的。在此基础上我们又给出paired-domina tion problem在strongly chordal graphs上线性时间算法。.（3）证明平面图和分裂图问题是NP-complete; 同时又证明了对即使对最大度不超过3的图而言,restrained domination 问题也APX-complete。.本项目也证明了张镇华教授1989年提出关于（t,n）-family中SDR数目的一个猜想。

项目成果

期刊论文数量（9）
专著数量（0）
科研奖励数量（0）
会议论文数量（0）
专利数量（0）
Labelling algorithms for paired-domination problems in block and interval graphs
块图和区间图中配对支配问题的标记算法
  • DOI：
    10.1007/s10878-008-9177-6
  • 发表时间：
    2008-02
  • 期刊：
    Journal of Combinatorial Optimization
  • 影响因子：
    1
  • 作者：
    Chen, Lei;Lu, Changhong;Zeng, Zhenbing
  • 通讯作者：
    Zeng, Zhenbing
THE L(2,1)-F-LABELING PROBLEM OF GRAPHS
图的 L(2,1)-F 标记问题
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
    Taiwanese Journal of Mathematics
  • 影响因子：
    0.4
  • 作者：
    Chang, Gerard J.;Lu, Changhong
  • 通讯作者：
    Lu, Changhong
Identifying codes and locating-dominating sets on paths and cycles
识别代码并定位路径和循环上的主导集
  • DOI：
    10.1016/j.dam.2011.06.008
  • 发表时间：
    2009-08
  • 期刊：
    Discrete Applied Mathematics
  • 影响因子：
    1.1
  • 作者：
    Chen, Chunxia;Lu, Changhong;Miao, Zhengke
  • 通讯作者：
    Miao, Zhengke
NP-completeness and APX-completeness of restrained domination in graphs
图中受限支配的 NP 完备性和 APX 完备性
  • DOI：
    10.1016/j.tcs.2012.05.005
  • 发表时间：
    2012-08
  • 期刊：
    Theoretical Computer Science
  • 影响因子：
    1.1
  • 作者：
    Chen, Lei;Zeng, Weiming;Lu, Changhong
  • 通讯作者：
    Lu, Changhong
A linear-time algorithm for paired-domination problem in strongly chordal graphs
强弦图中配对支配问题的线性时间算法
  • DOI：
    10.1016/j.ipl.2009.09.014
  • 发表时间：
    2009-12
  • 期刊：
    Information Processing Letters
  • 影响因子：
    0.5
  • 作者：
    Chen, Lei;Lu, Changhong;Zeng, Zhenbing
  • 通讯作者：
    Zeng, Zhenbing

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

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

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

{{ item.title }}
  • 作者：
    {{ item.authors }}

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

{{ item.title }}
  • 作者：
    {{ item.authors }}

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

{{ item.title }}
  • 作者：
    {{ item.authors }}

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

{{ item.title }}
  • 作者：
    {{ item.authors }}

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

其他文献

集装箱码头桥机调度问题基于完工时间下界的算法
  • DOI：
    10.15960/j.cnki.issn.1007-6093.2020.03.005
  • 发表时间：
    2020
  • 期刊：
    运筹学学报
  • 影响因子：
    --
  • 作者：
    陆书翔;吕长虹;秦涛
  • 通讯作者：
    秦涛
有向图的L(j,k)数的上界(英文)
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
    运筹学学报
  • 影响因子：
    --
  • 作者：
    翟明清;吕长虹
  • 通讯作者：
    吕长虹
度为奇数的正则图的上负全控制数
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
    应用数学学报
  • 影响因子：
    --
  • 作者：
    吴建刚;苗正科;吕长虹
  • 通讯作者：
    吕长虹
The geodetic numbers of Cartes
笛卡尔大地测量数
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
  • 影响因子：
    --
  • 作者：
    叶永升*;吕长虹;刘庆敏
  • 通讯作者：
    刘庆敏
双圈连通图的L(2，1)-labelling(英文)
  • DOI：
    --
  • 发表时间：
    --
  • 期刊：
    运筹学学报
  • 影响因子：
    --
  • 作者：
    吕长虹;翟明清
  • 通讯作者：
    翟明清

其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI：
    {{ item.doi || "--" }}
  • 发表时间：
    {{ item.publish_year || "--"}}
  • 期刊：
    {{ item.journal_name }}
  • 影响因子：
    {{ item.factor || "--" }}
  • 作者：
    {{ item.authors }}
  • 通讯作者：
    {{ item.author }}
empty
内容获取失败，请点击重试
重试联系客服
title开始分析
查看分析示例
此项目为已结题，我已根据课题信息分析并撰写以下内容，帮您拓宽课题思路：

AI项目思路

AI技术路线图

吕长虹的其他基金

码头自动化中的图论和组合优化问题
  • 批准号：
    12331014
  • 批准年份：
    2023
  • 资助金额：
    194 万元
  • 项目类别：
    重点项目
图（超图）的子图存在性问题研究
  • 批准号：
    11871222
  • 批准年份：
    2018
  • 资助金额：
    50.0 万元
  • 项目类别：
    面上项目
超图的2-可染色性和图的控制集问题
  • 批准号：
    11371008
  • 批准年份：
    2013
  • 资助金额：
    50.0 万元
  • 项目类别：
    面上项目
图的标号问题与子图存在性的理论和算法研究
  • 批准号：
    60673048
  • 批准年份：
    2006
  • 资助金额：
    25.0 万元
  • 项目类别：
    面上项目
图的标号问题和网络可靠性的图论研究
  • 批准号：
    10301010
  • 批准年份：
    2003
  • 资助金额：
    7.0 万元
  • 项目类别：
    青年科学基金项目

相似国自然基金

{{ item.name }}
  • 批准号：
    {{ item.ratify_no }}
  • 批准年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}

相似海外基金

{{ item.name }}
{{ item.translate_name }}
  • 批准号：
    {{ item.ratify_no }}
  • 财政年份：
    {{ item.approval_year }}
  • 资助金额：
    {{ item.support_num }}
  • 项目类别：
    {{ item.project_type }}
{{ showInfoDetail.title }}

作者：{{ showInfoDetail.author }}

知道了

AI项目解读示例

课题项目：调控A型流感病毒诱导IFN-β表达的机制研究

AI项目摘要：

本研究聚焦于TRIM2蛋白在A型流感病毒诱导的IFN-β表达中的调控机制。A型流感病毒是全球性健康问题，其感染可导致严重的呼吸道疾病。IFN-β作为关键的抗病毒因子，其表达水平对抗病毒防御至关重要。然而，TRIM2如何调控IFN-β的表达尚未明确。本研究假设TRIM2通过与病毒RNA或宿主因子相互作用，影响IFN-β的产生。我们将采用分子生物学、细胞生物学和免疫学方法，探索TRIM2与A型流感病毒诱导IFN-β表达的关系。预期结果将揭示TRIM2在抗病毒免疫反应中的作用，为开发新的抗病毒策略提供理论基础。该研究对理解宿主抗病毒机制具有重要科学意义，并可能对临床治疗流感病毒感染提供新的视角。

AI项目思路：

科学问题：TRIM2如何调控A型流感病毒诱导的IFN-β表达？
前期研究：已有研究表明TRIM2参与抗病毒反应，但其具体机制尚不明确。
研究创新点：本研究将深入探讨TRIM2在IFN-β表达中的直接作用机制。
技术路线：包括病毒学、分子生物学、细胞培养和免疫检测技术。
关键技术：TRIM2与病毒RNA的相互作用分析，IFN-β启动子活性检测。
实验模型：使用A型流感病毒感染的细胞模型进行研究。

AI技术路线图

        graph TD
          A[研究起始] --> B[文献回顾与假设提出]
          B --> C[实验设计与方法学准备]
          C --> D[A型流感病毒感染模型建立]
          D --> E[TRIM2与病毒RNA相互作用分析]
          E --> F[TRIM2对IFN-β启动子活性的影响]
          F --> G[IFN-β表达水平测定]
          G --> H[TRIM2功能丧失与获得研究]
          H --> I[数据收集与分析]
          I --> J[结果解释与科学验证]
          J --> K[研究结论与未来方向]
          K --> L[研究结束]
关闭
close
客服二维码