\input zb-basic
\input zb-ioport
\iteman{io-port 05344648}
\itemau{Salamon, G\'abor}
\itemti{Approximation algorithms for the maximum internal spanning tree problem.}
\itemso{Ku\v cera, Lud\v ek (ed.) et al., Mathematical foundations of computer science 2007. 32nd international symposium, MFCS 2007, \v Cesk\'y Krumlov, Czech Republic, August 26--31, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74455-9/pbk). Lecture Notes in Computer Science 4708, 90-102 (2007).}
\itemab
Summary: We consider the MaximumInternalSpanningTree problem which is to find a spanning tree of a given graph with a maximum number of non-leaf nodes. From an optimization point of view, this problem is equivalent to the MinimumLeafSpanningTree problem, and is NP-hard as being a generalization of the HamiltonianPath problem. Although there is no constant factor approximation for the MinimumLeafSpanningTree problem, MaximumInternalSpanningTree can be approximated within a factor of 2. In this paper we improve this factor by giving a $\frac{7}{4}$-approximation algorithm. We also investigate the node-weighted case, when the weighted sum of the internal nodes is to be maximized. For this problem, we give a $(2\Delta - 3)$-approximation for general graphs, and a 2-approximation for claw-free graphs. All our algorithms are based on local improvement steps.
\itemrv{~}
\itemcc{}
\itemut{approximation algorithm; spanning tree leaves; Hamiltonian path}
\itemli{doi:10.1007/978-3-540-74456-6\_10}
\end