| Revue: | Computación y sistemas |
| Base de datos: | |
| Número de sistema: | 000560709 |
| ISSN: | 1405-5546 |
| Autores: | López Medina, Marco Antonio1 González Ruiz, J. Leonardo1 Marcial Romero, J.Raymundo1 Hernández, J. A.1 |
| Instituciones: | 1Universidad Autónoma del Estado de México, Facultad de Ingeniería, México |
| Año: | 2022 |
| Periodo: | Abr-Jun |
| Volumen: | 26 |
| Número: | 2 |
| Paginación: | 815-822 |
| País: | México |
| Idioma: | Inglés |
| Resumen en inglés | The clique-width ( c w d ) is an invariant of graphs which, similar to other invariants like the tree-width ( t w d ) establishes a parameter for the complexity of a problem. For example, several problems with bounded clique-width can be solved in polynomial time. There is a well known relation between tree-width and clique-width denoted as c w d ( G ) ≤ 3 ⋅ 2 t w d ( G ) − 1. Serial-parallel graphs have tree-width of at most 2, so its clique–width is at most 6 according to the previous relation. In this paper, we improve the bound for this particular case, showing that the clique-width of series-parallel graphs is smaller or equal to 5. |
| Keyword: | Graph theory, Clique-width, Tree-width, Complexity, Series-parallel |
| Texte intégral: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
