On maximum independent sets in P5-free graphs
| Autor: | Ingo Schiermeyer, Bert Randerath |
|---|---|
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Lévy family of graphs Applied Mathematics Trapezoid graph Longest path problem Combinatorics Indifference graph Pathwidth Chordal graph Independent set Discrete Mathematics and Combinatorics Maximal independent set GeneralLiterature_REFERENCE(e.g. dictionaries encyclopedias glossaries) MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete Applied Mathematics. 158:1041-1044 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2010.01.007 |
| Popis: | The complexity status of the Maximum Independent Set Problem (MIS) for the family of P"5-free graphs is unknown. Although for many subclasses of P"5-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 P"5-free graphs in subexponential time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect