A linear time algorithm for the longest (s-t)-path problem restricted to partial k-trees

dc.contributor.author	Mata-Montero, M
dc.contributor.author	Ellis, JA
dc.date.accessioned	2018-05-30T08:35:29Z
dc.date.available	2018-05-30T08:35:29Z
dc.date.issued	1994
dc.identifier.citation	Mata-Montero M & Ellis JA (1994) A linear time algorithm for the longest (s-t)-path problem restricted to partial k-trees. South African Computer Journal, Number 12, 1994	en
dc.identifier.issn	2313-7835
dc.identifier.uri	http://hdl.handle.net/10500/24152
dc.description.abstract	The Longest (s-t)-path Problem, a known NP-complete set, is shown to admit a linear time solution when the instances of the problem are restricted to partial k-trees. This class of graphs is defined and some of the properties of partial k-trees, those needed for our algorithm are proved.	en
dc.language.iso	en	en
dc.publisher	South African Computer Society (SAICSIT)	en
dc.subject	Bounded treewidth	en
dc.subject	Partial k-trees	en
dc.subject	Longest path	en
dc.subject	Linear time algorithms	en
dc.title	A linear time algorithm for the longest (s-t)-path problem restricted to partial k-trees	en