圖的標號問題與子圖存在性的理論和算法研究

《圖的標號問題與子圖存在性的理論和算法研究》是依託華東師範大學，由呂長虹擔任項目負責人的面上項目。

基本介紹

• 中文名：圖的標號問題與子圖存在性的理論和算法研究
• 項目類別：面上項目
• 項目負責人：呂長虹
• 依託單位：華東師範大學
• 批准號：60673048
• 申請代碼：F0201
• 負責人職稱：教授
• 研究期限：2007-01-01 至 2009-12-31
• 支持經費：25（萬元）

項目摘要

圖論中的標號問題來源於通訊中的頻道分配問題(channel assignment problem),亦是圖論經典著色問題的推廣，在理論和套用方面均有其積極意義。因此各種形式的標號問題目前為眾多學者所關注。本項目主要考慮圖的L(j,k)-labeling ,T-coloring 等問題的性質及算法。圖中是否存在某種特定的結構或子圖是圖論研究的主流問題之一，也是計算機科學家在圖論算法研究的核心問題。我們將研究盒中的蛇（Snake-in-the-box）、圖譜理論、路分解、二部圖中子圖存在性等問題.