學術產出-期刊論文

文章檢視/開啟

書目匯出

Google ScholarTM

政大圖書館

引文資訊

TAIR相關學術產出

題名 Parallel algorithms for connected domination problem on interval and circular-arc graphs.
作者 Hsu, F.R.
沈錳坤
Shan, M.K.
貢獻者 資科系
關鍵詞 Connected Domination Set; Interval Graph; Circular-arc Graph
日期 2002
上傳時間 28-九月-2018 17:01:00 (UTC+8)
摘要 A connected domination set of a graph is a set of vertices such that every vertex not in is adjacent to and the induced subgraph of is connected. The minimum connected domination set of a graph is the connected domination set with the minimum number of vertices. In this paper, we propose parallel algorithms for finding the minimum connected domination set of interval graphs and circular-arc graphs. Our algorithms run in time algorithm using processors while the intervals and arcs are given in sorted order. Our algorithms are on the EREW PRAM model.
關聯 WSEAS Transactions on Mathematics (WSEAS Trans. Math.) (20020101), 1, no.~1-4, 83-88
AMS MathSciNet:MR2009353
資料類型 article
dc.contributor 資科系
dc.creator (作者) Hsu, F.R.en_US
dc.creator (作者) 沈錳坤zh_TW
dc.creator (作者) Shan, M.K.en_US
dc.date (日期) 2002
dc.date.accessioned 28-九月-2018 17:01:00 (UTC+8)-
dc.date.available 28-九月-2018 17:01:00 (UTC+8)-
dc.date.issued (上傳時間) 28-九月-2018 17:01:00 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/120203-
dc.description.abstract (摘要) A connected domination set of a graph is a set of vertices such that every vertex not in is adjacent to and the induced subgraph of is connected. The minimum connected domination set of a graph is the connected domination set with the minimum number of vertices. In this paper, we propose parallel algorithms for finding the minimum connected domination set of interval graphs and circular-arc graphs. Our algorithms run in time algorithm using processors while the intervals and arcs are given in sorted order. Our algorithms are on the EREW PRAM model.en_US
dc.format.extent 161 bytes-
dc.format.mimetype text/html-
dc.relation (關聯) WSEAS Transactions on Mathematics (WSEAS Trans. Math.) (20020101), 1, no.~1-4, 83-88
dc.relation (關聯) AMS MathSciNet:MR2009353
dc.subject (關鍵詞) Connected Domination Set; Interval Graph; Circular-arc Graphen_US
dc.title (題名) Parallel algorithms for connected domination problem on interval and circular-arc graphs.en_US
dc.type (資料類型) article