An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs

Sun Yuan Hsieh, Gen Huey Chen, Chin Wen Ho

研究成果: 書貢獻/報告類型會議論文篇章同行評審

摘要

In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex distance-hereditary graph G, we show that the perfect dominating set problem on G can be solved in O(log2 n) time using O(n+m) procesors on a CREW PRAM.

原文???core.languages.en_GB???
主出版物標題Advances in Computing Science ASIAN 1998 - 4th Asian Computing Science Conference, Proceedings
編輯Jieh Hsiang, Atsushi Ohori
發行者Springer Verlag
頁面113-124
頁數12
ISBN(列印)3540653880, 9783540653882
DOIs
出版狀態已出版 - 1998
事件4th Asian Computing Science Conference, ASIAN 1998 - Manila, Philippines
持續時間: 8 12月 199810 12月 1998

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
1538
ISSN(列印)0302-9743
ISSN(電子)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???4th Asian Computing Science Conference, ASIAN 1998
國家/地區Philippines
城市Manila
期間8/12/9810/12/98

指紋

深入研究「An optimal parallel algorithm for the perfect dominating set problem on distance-hereditary graphs」主題。共同形成了獨特的指紋。

引用此