| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420375 | Discrete Applied Mathematics | 2010 | 4 Pages |
Abstract
The complexity status of the Maximum Independent Set Problem (MIS) for the family of P5P5-free graphs is unknown. Although for many subclasses of P5P5-free graphs MIS can be solved in polynomial time, only exponential time MIS-algorithms for general graphs are known so far. In this note we present the first algorithm to solve MIS for P5P5-free graphs in subexponential time.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Bert Randerath, Ingo Schiermeyer,