A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs
| dc.contributor.author | Bonsma, Paul | |
| dc.contributor.author | Zickfeld, Florian | |
| dc.date.accessioned | 2021-12-17T10:08:01Z | |
| dc.date.available | 2021-12-17T10:08:01Z | |
| dc.date.issued | 2008 | |
| dc.description.abstract | We consider the problem of finding a spanning tree that maximizes the number of leaves (Max Leaf). We provide a 3/2-approximation algorithm for this problem when restricted to cubic graphs, improving on the previous 5/3-approximation for this class. To obtain this approximation we define a graph parameter x(G), and construct a tree with at least (n-x(G)+4)/3 leaves, and prove that no tree with more than (n-x(G)+2)/2 leaves exists. In contrast to previous approximation algorithms for Max Leaf, our algorithm works with connected dominating sets instead of constructing a tree directly. The algorithm also yields a 4/3-approximation for Minimum Connected Dominating Set in cubic graphs. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15645 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14418 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | spanning tree | en |
| dc.subject.other | max leaf | en |
| dc.subject.other | approximation | en |
| dc.subject.other | cubic graph | en |
| dc.title | A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2008, 15 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1