Efficient algorithms for the hamiltonian problem on distance-hereditary graphs

Sun Yuan Hsieh, Chin Wen Ho, Tsan Sheng Hsu, Ming Tat Ko

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

8 引文 斯高帕斯(Scopus)

摘要

In this paper, we first present an O(|V | + |E|)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G = (V,E). This algorithm is faster than the previous best result which takes O(|V|2) time. Let Td(|V|, |E|) and Pd(|V|, |E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph on a PRAM model Md.We also show that this problem can be solved in O(Td(|V|,|E|) + log |V|) time using O(Pd(|V|, |E|) + (|V | + |E|)/ log |V |) processors on Md. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log |V |) time using O((|V | + |E|)/ log |V |) processors on an EREW PRAM.

原文???core.languages.en_GB???
主出版物標題Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings
編輯Oscar H. Ibarra, Louxin Zhang
發行者Springer Verlag
頁面77-86
頁數10
ISBN(列印)354043996X, 9783540439967
DOIs
出版狀態已出版 - 2002
事件8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore
持續時間: 15 8月 200217 8月 2002

出版系列

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

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

???event.eventtypes.event.conference???8th Annual International Conference on Computing and Combinatorics, COCOON 2002
國家/地區Singapore
城市Singapore
期間15/08/0217/08/02

指紋

深入研究「Efficient algorithms for the hamiltonian problem on distance-hereditary graphs」主題。共同形成了獨特的指紋。

引用此