Paired-Domination on Distance-Hereditary Graphs and Its Related Problems

瀏覽統計 Email 通知 RSS Feed

簡歷

基本資料

Project title

Code/計畫編號

MOST111-2221-E019-054

Translated Name/計畫中文名

保距圖上的「成對支配點問題」及其相關問題

Project Coordinator/計畫主持人

Ching-Chi Lin

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

Department of Computer Science and Engineering

Website

https://www.grb.gov.tw/search/planDetail?id=14520192

Year

2022

Start date/計畫起

01-08-2022

Expected Completion/計畫迄

31-07-2023

Bugetid/研究經費

700千元

ResearchField/研究領域

資訊科學--軟體

本計畫主要探討保距圖 (distance-hereditary graph)、圓形圖 (circle graph) 以及平面圖 (planar graph) 上的成對支配點問題，預計在保距圖上設計 O(n) 時間的演算法與證明成對支配點問題在圓形圖與平面圖上均為 NP-complete，並設計平面圖與圓形圖上的近似演算法。成對支配點問題不但在演算法的設計與分析上扮演著重要角色，同時在通訊網路與資源分配的設計與分析上也有相當重要的實際應用。計畫完成後，預計將結果發表在 Algorithmica 與 TCS 等演算法頂尖期刊與 ISAAC 與 COCOON 等頂級國際會議上。

Keyword(s)

成對支配點問題
完美匹配
保距圖
圓形圖
平面圖
近似演算法
NP完全
paired-domination problem
perfect matching
distance-hereditary graphs
circle graph
planar graph
approximation algorithm
NP-complete

DSpace CRIS

Paired-Domination on Distance-Hereditary Graphs and Its Related Problems

基本資料

Description