The Library
Parameterized algorithms for the independent set problem in some hereditary graph classes
Tools
Dabrowski, Konrad, Lozin, Vadim V., Muller, H. and Rautenbach, Dieter (2011) Parameterized algorithms for the independent set problem in some hereditary graph classes. In: 21st International Workshop on Combinatorial Algorithms, KCL Dept Informat, London, England, 26-28 Jul 2010 . Published in: Lecture Notes in Computer Science, Vol.6460 pp. 1-9. doi:10.1007/978-3-642-19222-7_1 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://springerlink.com/content/105633/
Abstract
The maximum independent set problem is NP-complete for graphs in general, but becomes solvable in polynomial time when restricted to graphs in many special classes. The problem is also intractable from a parameterized point of view. However, very little is known about parameterized complexity of the problem in restricted graph classes. in the present paper, we analyse two techniques that have previously been used to solve the problem in polynomial time for graphs in particular classes and apply these techniques to develop fpt-algorithms for graphs in some classes where the problem remains NP-complete.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Lecture Notes in Computer Science | ||||
Publisher: | Springer | ||||
ISSN: | 0302-9743 | ||||
Official Date: | 2011 | ||||
Dates: |
|
||||
Volume: | Vol.6460 | ||||
Page Range: | pp. 1-9 | ||||
DOI: | 10.1007/978-3-642-19222-7_1 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 21st International Workshop on Combinatorial Algorithms | ||||
Type of Event: | Workshop | ||||
Location of Event: | KCL Dept Informat, London, England | ||||
Date(s) of Event: | 26-28 Jul 2010 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |