Name
Abstract | ||
|---|---|---|
The weighted independent set problem on P5-free graphs has numerous applications, including data mining and dispatching in railways. The recognition of P5-free graphs is executed in polynomial time. Many problems, such as chromatic number and dominating set, are NP-hard in the class of P5-free graphs. The size of a minimum independent feedback vertex set that belongs to a P5-free graph with n vertices can be computed in O(n16) time. The unweighted problems, clique and clique cover, are NP-complete and the independent set is polynomial. In this work, the P5-free graphs using the weak decomposition are characterized, as is the dominating clique, and they are given an O(n(n+m)) recognition algorithm. Additionally, we calculate directly the clique number and the chromatic number; determine in O(n) time, the size of a minimum independent feedback vertex set; and determine in O(n+m) time the number of stability, the dominating number and the minimum clique cover. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.3390/sym12020304 | SYMMETRY-BASEL |
Keywords | DocType | Volume |
P-5-free graphs,weak decomposition,recognition algorithm,optimization algorithm,symmetric graph | Journal | 12 |
Issue | Citations | PageRank |
2 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mihai Talmaciu | 1 | 4 | 2.83 |
| Luminita Dumitriu | 2 | 1 | 3.39 |
| Ioan Susnea | 3 | 1 | 2.72 |
| Victor Lepin | 4 | 0 | 0.34 |
| Barna Laszlo Iantovics | 5 | 19 | 8.47 |