  Finding spanning trees under various constraints is a classic problem with
applications in many fields. Recently, a novel notion of "dense" ("sparse")
tree, and in particular spanning tree (DST and SST respectively), is introduced
as the structure that have a large (small) number of subtrees, or small (large)
sum of distances between vertices. We show that finding DST and SST reduces to
solving the discrete optimization problems. New and efficient approaches to
find such spanning trees is achieved by imposing certain conditions on the
vertex degrees which are then used to define an objective function that is
minimized over all spanning trees of the graph under consideration. Solving
this minimization problem exactly may be prohibitively time consuming for large
graphs. Hence, we propose to use genetic algorithm (GA) which is one of well
known metaheuristics methods to solve DST and SST approximately. As far as we
are aware this is the first time GA has been used in this context. We also
demonstrate on a number of applications that GA approach is well suited for
these types of problems both in computational efficiency and accuracy of the
approximate solution. Furthermore, we improve the efficiency of the proposed
method by using Kruskal's algorithm in combination with GA.
  The application of our methods to several practical large graphs and networks
is presented. Computational results show that they perform faster than
previously proposed heuristic methods and produce more accurate solutions.
Furthermore, the new feature of the proposed approach is that it can be applied
recursively to sub-trees or spanning trees with additional constraints in order
to further investigate the graphical properties of the graph and/or network.
The application of this methodology on the gene network of a cancer cell led to
isolating key genes in a network that were not obvious from previous studies.
