Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



A 5/3-approximation for finding spanning trees with many leaves in cubic graphs
Indexado
WoS WOS:000253668000015
DOI
Año 2008
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



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.

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Computer Science (All)
Theoretical Computer Science
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



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 -

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
CNPq
CONICYT (Chile) through Anillo en Redes
ProNEx - FAPESP/CNPq

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
Research partially supported by CONICYT (Chile) through Anillo en Redes ACT08. Research partially supported by CNPq (Proc. 490333/04, 307011/03-8, 308138/04-0) and ProNEx - FAPESP/CNPq Proc. No. 2003/09925-5 (Brazil).

Muestra la fuente de financiamiento declarada en la publicación.