Muestra la distribución de disciplinas para esta publicación.
Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.
| Indexado |
|
||
| DOI | |||
| Año | 2008 | ||
| Tipo | proceedings paper |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
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.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | CORREA-FONTECILLA, JOSE RAFAEL | Hombre |
Universidad Adolfo Ibáñez - Chile
|
| 2 | Fernandes, Cristina G. | Mujer |
Universidade Sao Paulo - Brasil
|
| 3 | MATAMALA-VASQUEZ, MARTIN IGNACIO | Hombre |
Universidad de Chile - Chile
|
| 4 | Wakabayashi, Yoshiko | Mujer |
Universidade Sao Paulo - Brasil
|
| 5 | Kaklamanis, C | - | |
| 6 | Skutella, M | - |