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: | (VoR) Version of Record Download PDF (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/ |
| Date accepted: | No date available |
| Date deposited: | 07 October 2010 |
| Date of first online publication: | 2010 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
