The longest path problem on distance-hereditary graphs

Yi Lu Guo; Chin Wen Ho; Ming Tat Ko

doi:10.1007/978-3-642-35452-6_9

The longest path problem on distance-hereditary graphs

Yi Lu Guo, Chin Wen Ho, Ming Tat Ko

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

2 Scopus citations

Abstract

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.

Original language	English
Title of host publication	Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan
Editors	Jain Lakhmi, Chang Ruay-Shiung, Peng Sheng-Lung
Pages	69-77
Number of pages	9
DOIs	https://doi.org/10.1007/978-3-642-35452-6_9
State	Published - 2013

Publication series

Name	Smart Innovation, Systems and Technologies
Volume	20
ISSN (Print)	2190-3018
ISSN (Electronic)	2190-3026

Keywords

Distance-hereditary graphs
Longest path problem
Polynomialtime algorithm

Access to Document

10.1007/978-3-642-35452-6_9

Cite this

Guo, Y. L., Ho, C. W., & Ko, M. T. (2013). The longest path problem on distance-hereditary graphs. In J. Lakhmi, C. Ruay-Shiung, & P. Sheng-Lung (Eds.), Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan (pp. 69-77). (Smart Innovation, Systems and Technologies; Vol. 20). https://doi.org/10.1007/978-3-642-35452-6_9

@inbook{77f1699bb5a24afc9417b4727ad7ff80,

title = "The longest path problem on distance-hereditary graphs",

abstract = "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.",

keywords = "Distance-hereditary graphs, Longest path problem, Polynomialtime algorithm",

author = "Guo, {Yi Lu} and Ho, {Chin Wen} and Ko, {Ming Tat}",

year = "2013",

doi = "10.1007/978-3-642-35452-6_9",

language = "???core.languages.en_GB???",

isbn = "9783642354519",

series = "Smart Innovation, Systems and Technologies",

pages = "69--77",

editor = "Jain Lakhmi and Chang Ruay-Shiung and Peng Sheng-Lung",

booktitle = "Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan",

}

Guo, YL, Ho, CW & Ko, MT 2013, The longest path problem on distance-hereditary graphs. in J Lakhmi, C Ruay-Shiung & P Sheng-Lung (eds), Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan. Smart Innovation, Systems and Technologies, vol. 20, pp. 69-77. https://doi.org/10.1007/978-3-642-35452-6_9

The longest path problem on distance-hereditary graphs. / Guo, Yi Lu; Ho, Chin Wen; Ko, Ming Tat.
Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan. ed. / Jain Lakhmi; Chang Ruay-Shiung; Peng Sheng-Lung. 2013. p. 69-77 (Smart Innovation, Systems and Technologies; Vol. 20).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - The longest path problem on distance-hereditary graphs

AU - Guo, Yi Lu

AU - Ho, Chin Wen

AU - Ko, Ming Tat

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Distance-hereditary graphs

KW - Longest path problem

KW - Polynomialtime algorithm

UR - http://www.scopus.com/inward/record.url?scp=84879311501&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-35452-6_9

DO - 10.1007/978-3-642-35452-6_9

M3 - 篇章

AN - SCOPUS:84879311501

SN - 9783642354519

T3 - Smart Innovation, Systems and Technologies

SP - 69

EP - 77

BT - Advances in Intelligent Systems and Applications -Volume 1 Proceedings of the International Computer Symposium ICS 2012 Held at Hualien,Taiwan

A2 - Lakhmi, Jain

A2 - Ruay-Shiung, Chang

A2 - Sheng-Lung, Peng

ER -

The longest path problem on distance-hereditary graphs

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this