The Library
Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
Tools
Tools
Tools
Dabrowski, Konrad, Lozin, Vadim V., Müller, Haiko and Rautenbach, Dieter (2012) Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. Journal of Discrete Algorithms, Vol.14 . pp. 207-213. doi:10.1016/j.jda.2011.12.012 ISSN 1570-8667.
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://dx.doi.org/10.1016/j.jda.2011.12.012
Abstract
The maximum independent set problem is known to be NP-hard for graphs in general, but is solvable in polynomial time for graphs in many special classes. It is also known that the problem is generally intractable from a parameterized point of view. A simple Ramsey argument implies the fixed-parameter tractability of the maximum independent set problem in classes of graphs of bounded clique number. Beyond this observation very little is known about the parameterized complexity of the problem in restricted graph families. In the present paper we develop fpt-algorithms for graphs in some classes extending graphs of bounded clique number.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | Journal of Discrete Algorithms | ||||
| Publisher: | Elsevier BV | ||||
| ISSN: | 1570-8667 | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Volume: | Vol.14 | ||||
| Page Range: | pp. 207-213 | ||||
| DOI: | 10.1016/j.jda.2011.12.012 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Description: | Selected papers from the 21st International Workshop on Combinatorial Algorithms (IWOCA 2010) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
