| Texto completo | |
| Autor(es): |
Botler, F.
;
Cano, R.
;
Sambinelli, M.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 346, p. 13-pg., 2019-08-30. |
| Resumo | |
Gallai (1966) conjectured that the edge set of every graph G on n vertices can be covered by at most [n/2] edge-disjoint paths. Such a covering by edge-disjoint paths is called a path decomposition, and the size of a path decomposition with a minimum number of elements is called the path number of G. Peroche (1984) proved that the problem of computing the path number is NP-Complete; and Constantinou and Ellinas (2018) proved that it is polynomial for a family of complete bipartite graphs. In this paper we present an integer Linear Programming model for computing the path number of a graph. This allowed us to verify Gallai's Conjecture for a large collection of graphs. As a result, following a work of Heinrich, Natale and Streicher on cycle decompositions (2017), we verify Gallai's Conjecture for graphs with at most 11 vertices; for bipartite graphs with at most 16 vertices; and for regular graphs with at most 14 vertices. (AU) | |
| Processo FAPESP: | 17/23623-4 - Problemas de partição em grafos e dígrafos |
| Beneficiário: | Maycon Sambinelli |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |