Paper Info
Title
A Survey on Algorithms for the Maximum Internal Spanning Tree and Related Problems
Abstract
Given an undirected connected graph G we consider the problem of finding a spanning tree of G with a maximum number of internal ( ⩾ 2 degree) vertices. This problem, called the Maximum Internal Spanning Tree problem, is obviously NP-hard since it generalizes the Hamiltonian Path problem. In this paper we aim at giving a survey on recent results about the Maximum Internal Spanning Tree problem including different approaches such as exact exponential algorithms, fixed parameter tractability, and approximation algorithms. We also consider the problem of finding a large ( ⩽ q )-leaf subtree of the input graph for some fixed q . Keywords Spanning tree leaves Hamiltonian path approximation algorithm
Year
DOI
Venue
2010
10.1016/j.endm.2010.05.153
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
hamiltonian path problem,hamiltonian path,approximation algorithm,spanning tree,connected graph
Discrete mathematics,Combinatorics,Steiner tree problem,k-minimum spanning tree,Algorithm,Euclidean minimum spanning tree,Spanning tree,Connected dominating set,Shortest-path tree,Gomory–Hu tree,Mathematics,Minimum spanning tree
Journal
Volume
ISSN
Citations 
36
Electronic Notes in Discrete Mathematics
8
PageRank 
References 
Authors
0.59
7
1
Name
Order
Citations
PageRank
Gábor Salamon1463.61