Fiala, J. and Kaminski, M. and Lidicky, B. and Paulusma, Daniel (2010) 'The k-in-a-path problem for claw-free graphs.', in 27th International symposium on theoretical aspects of computer science, STACS 2010, 4-6 March 2010 ; proceedings. Saarbrücken, Germany: Dagstuhl, 371-382 . Leibniz international proceedings in informatics. (5).
Abstract
Testing whether there is an induced path in a graph spanning $k$ given vertices is already \NP-complete in general graphs when $k=3$. We show how to solve this problem in polynomial time on claw-free graphs, when $k$ is not part of the input but an arbitrarily fixed integer.
| Item Type: | Book chapter |
|---|---|
| Keywords: | Induced path, Claw-free graph, Polynomial-time algorithm. |
| Full text: | PDF - Published Version (305Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2469 |
| Publisher statement: | This article is made available under a Creative Commons Attribution-No Derivative Works 3.0 Unported License. http://creativecommons.org/licenses/by-nd/3.0/ |
| Record Created: | 07 Oct 2010 12:20 |
| Last Modified: | 03 Apr 2013 16:17 |
Social bookmarking:       | Export: EndNote, Zotero | BibTex |
| Usage statistics | Look up in GoogleScholar | Find in a UK Library |
![[Feed]](/images/RSSwebsmall.jpg)
![[Tweets]](/images/Twitterwebsmall.png)
