The longest path problem on distance-hereditary graphs

Yi Lu Guo, Chin Wen Ho, Ming Tat Ko

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

1 引文 斯高帕斯(Scopus)

摘要

The longest path problem is to find a path of maximum length in a graph. As a generalization of Hamiltonian path problem, it is NP-complete on general graphs. A graph is called distance-hereditary if the distances of each pair of vertices in every connected induced subgraph containing them are the same. In this paper, we present an O(n4) time algorithm to solve the longest path problem on a distance-hereditary graph of n vertices.

原文???core.languages.en_GB???
主出版物標題Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan
編輯Jain Lakhmi, Chang Ruay-Shiung, Peng Sheng-Lung
頁面69-77
頁數9
DOIs
出版狀態已出版 - 2013

出版系列

名字Smart Innovation, Systems and Technologies
20
ISSN(列印)2190-3018
ISSN(電子)2190-3026

指紋

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

引用此