| Texto completo | |
| Autor(es): |
Correa, Jose R.
;
Fernandes, Cristina G.
;
Matamala, Martin
;
Wakabayashi, Yoshiko
;
Kaklamanis, C
;
Skutella, M
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | Lecture Notes in Computer Science; v. 4927, p. 3-pg., 2008-01-01. |
| Resumo | |
For a connected graph G, let L(G) denote the maximum number of leaves in a spanning tree in G. The problem of computing L(G) is known to be NP-hard even for cubic graphs. We improve on Lorys and Zwoiniak's result presenting a 5/3-approximation for this problem on cubic graphs. This result is a consequence of new lower and upper bounds for L(G) which are interesting on their own. We also show a lower bound for L(G) that holds for graphs with minimum degree at least 3. (AU) | |
| Processo FAPESP: | 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas |
| Beneficiário: | Yoshiharu Kohayakawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Programa PRONEX - Temático |