| Autor: |
Mihai Talmaciu, Luminiţa Dumitriu, Ioan Şuşnea, Victor Lepin, László Barna Iantovics |
| Jazyk: |
angličtina |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
Symmetry, Vol 12, Iss 2, p 304 (2020) |
| Druh dokumentu: |
article |
| ISSN: |
2073-8994 |
| DOI: |
10.3390/sym12020304 |
| Popis: |
The weighted independent set problem on P 5 -free graphs has numerous applications, including data mining and dispatching in railways. The recognition of P 5 -free graphs is executed in polynomial time. Many problems, such as chromatic number and dominating set, are NP-hard in the class of P 5 -free graphs. The size of a minimum independent feedback vertex set that belongs to a P 5 -free graph with n vertices can be computed in O ( n 16 ) time. The unweighted problems, clique and clique cover, are NP-complete and the independent set is polynomial. In this work, the P 5 -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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
|
Nepřihlášeným uživatelům se plný text nezobrazuje |
K zobrazení výsledku je třeba se přihlásit.
|
