Name
Abstract | ||
|---|---|---|
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph G, decides whether one can be transformed into the other by a sequence of elementary steps. Each elementary step is to remove a vertex v from the current independent set S and to add a new vertex w (not in S) such that the result is again an independent set. We also consider the more restricted model where v and w have to be adjacent. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-08404-6_8 | ALGORITHM THEORY - SWAT 2014 |
Field | DocType | Volume |
Claw,Discrete mathematics,Combinatorics,Vertex (geometry),Claw-free graph,Vertex (graph theory),Neighbourhood (graph theory),Independent set,Feedback vertex set,Mathematics,Maximal independent set | Journal | 8503 |
ISSN | Citations | PageRank |
0302-9743 | 20 | 1.05 |
References | Authors | |
24 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Bonsma | 1 | 287 | 20.46 |
| Marcin Kaminski | 2 | 314 | 32.38 |
| Marcin Wrochna | 3 | 47 | 7.61 |