Name
Abstract | ||
|---|---|---|
The problem of finding a spanning tree with few leaves is motivated by the design of communication networks, where the cost of the devices depends on their routing functionality (ending, forwarding, or routing a connection). Besides this application, the problem has its own theoretical importance as a generalization of the Hamiltonian path problem. Lu and Ravi showed that there is no constant factor approximation for minimizing the number of leaves of a spanning tree, unless P=NP. Thus instead of minimizing the number of leaves, we are going to deal with maximizing the number of non-leaves: we give a linear-time 2-approximation for arbitrary graphs, a 32-approximation for claw-free graphs, and a 65-approximation for cubic graphs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ipl.2007.08.030 | Inf. Process. Lett. |
Keywords | Field | DocType |
routing functionality,constant factor approximation,cubic graph,arbitrary graph,hamiltonian path problem,claw-free graph,own theoretical importance,communication network,approximation algorithms,claw free graph,linear time,spanning tree,spanning trees | Discrete mathematics,Approximation algorithm,Combinatorics,Minimum degree spanning tree,k-minimum spanning tree,Hamiltonian path,Hamiltonian path problem,Spanning tree,Time complexity,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
105 | 5 | 0020-0190 |
Citations | PageRank | References |
28 | 1.45 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Salamon | 1 | 46 | 3.61 |
| Gábor Wiener | 2 | 64 | 10.65 |