The Hamiltonian problem on distance-hereditary graphs

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

研究成果: Article同行評審

13 引文 斯高帕斯(Scopus)

摘要

In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n2) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM.

原文English
頁(從 - 到)508-524
頁數17
期刊Discrete Applied Mathematics
154
發行號3
DOIs
出版狀態Published - 2006 三月 1

All Science Journal Classification (ASJC) codes

  • 離散數學和組合
  • 應用數學

指紋

深入研究「The Hamiltonian problem on distance-hereditary graphs」主題。共同形成了獨特的指紋。

引用此