Name
Abstract | ||
|---|---|---|
The maximum independent set problem is known to be NP-hard in the class of planar graphs. In the present paper, we study its complexity in hereditary subclasses of planar graphs. In particular, by combining various techniques, we show that the problem is polynomially solvable in the class of S1,2,k-free planar graphs, generalizing several previously known results. S1,2,k is the graph consisting of three induced paths of lengths 1, 2 and k, with a common initial vertex. |
Year | Venue | Keywords |
|---|---|---|
2010 | J. Graph Algorithms Appl. | maximum independent set,planar graph |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Independent set,Cograph,Pathwidth,1-planar graph,Mathematics,Maximal independent set | Journal | 14 |
Issue | Citations | PageRank |
2 | 10 | 0.56 |
References | Authors | |
17 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vadim Lozin | 1 | 99 | 7.13 |
| Martin Milaniÿc | 2 | 10 | 0.56 |
| Coventry CV | 3 | 22 | 2.87 |