Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

The k-in-a-path problem for claw-free graphs.

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: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library