| Full text | |
| Author(s): |
Correa, Jose R.
;
Fernandes, Cristina G.
;
Matamala, Martin
;
Wakabayashi, Yoshiko
;
Kaklamanis, C
;
Skutella, M
Total Authors: 6
|
| Document type: | Journal article |
| Source: | Lecture Notes in Computer Science; v. 4927, p. 3-pg., 2008-01-01. |
| 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. (AU) | |
| FAPESP's process: | 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | PRONEX Research - Thematic Grants |