| Journal: | Computación y sistemas |
| Database: | |
| System number: | 000560709 |
| ISSN: | 1405-5546 |
| Authors: | López Medina, Marco Antonio1 González Ruiz, J. Leonardo1 Marcial Romero, J.Raymundo1 Hernández, J. A.1 |
| Institutions: | 1Universidad Autónoma del Estado de México, Facultad de Ingeniería, México |
| Year: | 2022 |
| Season: | Abr-Jun |
| Volumen: | 26 |
| Number: | 2 |
| Pages: | 815-822 |
| Country: | México |
| Language: | Inglés |
| English abstract | 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 |
| Full text: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
