Maximum spanning k-trees
MetadataShow full item record
The spanning k-tree for bounded k is a notion extended from the spanning tree of a graph, which serves many applications ranging from network reliability to machine learning. k- trees are intimately related to graphs of bounded tree width; problems involving k-trees are potentially have efficient solutions. However, on given general graphs, the problem to produce a maximum spanning k-tree (MSkT) is NP-hard, even for k = 2, and remains intractable for many well-known restricted families of graphs. This thesis investigates effective models derived from MSkT, where efficient algorithms are designed to compute optimal and near optimal solutions with different objective func- tions defined on the models. The development of the models is motivated by the increasing real-world interests that seek answers about complex relations from given input data. This research is of particular interest to coping with the computational intractability that rou- tinely arises from problems in many emerging applications, such as bioinformatics, machine learning, big data analytics, and social networks. The success of the models has been based on non-conventional, non-trivial graph metrics that can well characterize many application problems and can lead to efficient graph optimization algorithms.