| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949498 | Discrete Applied Mathematics | 2017 | 6 Pages |
Abstract
The Maximum Independent Set Problem is known to be NP-hard in general. In the last decades lots of effort were spent to find polynomial-time algorithms for Pt-free graphs. A recent result presents such an algorithm for P5-free graphs. On the other hand, the complexity status for larger t is still unknown. In this paper we present a subexponential algorithm for the Maximum (Weighted) Independent Set Problem in Pt-free graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christoph Brause,