The longest path problem on distance-hereditary graphs

NCUIR > College of Electrical Engineering & Computer Science > Department of Computer Science and information Engineering > journal & Dissertation > Item 987654321/107426

Please use this identifier to cite or link to this item: https://ir.lib.ncu.edu.tw/handle/987654321/107426

Title:	The longest path problem on distance-hereditary graphs
Authors:	何錦文;Guo, Yi-Lu;Ho, Chin-Wen;Ko, Ming-Tat
Contributors:	資訊電機學院資訊工程學系
Keywords:	Distance-hereditary graphs;Longest path problem;Polynomial-time algorithm
Date:	2013-06-28
Issue Date:	2026-04-23 14:12:27 (UTC+8)
Publisher:	Springer Verlag;Berlin, Heidelberg: Springer Berlin Heidelberg
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. 出版者： Berlin, Heidelberg: Springer Berlin Heidelberg 出版日期： 2013 出處： Advances in Intelligent Systems and Applications - Volume 1, 2013, p.69-77 版權： Springer-Verlag Berlin Heidelberg 2013 識別號： ISSN: 2190-3018 識別號： ISBN: 9783642354519 識別號： ISBN: 3642354513 識別號： EISSN: 2190-3026 識別號： EISBN: 9783642354526 識別號： EISBN: 3642354521 識別號： DOI: 10.1007/978-3-642-35452-6_9
Appears in Collections:	[Department of Computer Science and information Engineering] journal & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	12	View/Open

社群 sharing