The Library
Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
Tools
Lozin, Vadim V. (2009) Parameterized complexity of the maximum independent set problem and the speed of hereditary properties. Electronic Notes in Discrete Mathematics, Vol.34 . pp. 127-131. doi:10.1016/j.endm.2009.07.021 ISSN 1571-0653.
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.endm.2009.07.021
Abstract
For a hereditary class X, the number Xn of n-vertex graphs in X (also known as the speed of X) satisfies where k(X) is a natural number called the index of the class. Each class X of index k>1 can be approximated by a minimal class of the same index. In this paper, we use Ramsey theory to show that the maximum independent set problem is fixed-parameter tractable in all minimal classes of index k for all values of k.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Electronic Notes in Discrete Mathematics | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 1571-0653 | ||||
Official Date: | 1 August 2009 | ||||
Dates: |
|
||||
Volume: | Vol.34 | ||||
Page Range: | pp. 127-131 | ||||
DOI: | 10.1016/j.endm.2009.07.021 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |