| Autor: |
Chuan-Min Lee |
| Jazyk: |
angličtina |
| Rok vydání: |
2024 |
| Předmět: |
|
| Zdroj: |
Axioms, Vol 13, Iss 6, p 382 (2024) |
| Druh dokumentu: |
article |
| ISSN: |
2075-1680 |
| DOI: |
10.3390/axioms13060382 |
| Popis: |
This paper explores the computational challenges of clique transversal problems in d-degenerate graphs, which are commonly encountered across theoretical computer science and various network applications. We examine d-degenerate graphs to highlight their utility in representing sparse structures and assess several variations of clique transversal problems, including the b-fold and {b}-clique transversal problems, focusing on their computational complexities for different graph categories. Our analysis identifies that certain instances of these problems are polynomial-time solvable in specific graph classes, such as 1-degenerate or 2-degenerate graphs. However, for d-degenerate graphs where d≥2, these problems generally escalate to NP-completeness. We also explore the parameterized complexity, pinpointing specific conditions that render these problems fixed-parameter tractable. |
| 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.
|
