Files
Abstract
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-treesare potentially have efficient solutions. However, on given general graphs, the problem toproduce a maximum spanning k-tree (MSkT) is NP-hard, even for k = 2, and remainsintractable for many well-known restricted families of graphs.This thesis investigates effective models derived from MSkT, where efficient algorithmsare 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 increasingreal-world interests that seek answers about complex relations from given input data. Thisresearch is of particular interest to coping with the computational intractability that rou-tinely arises from problems in many emerging applications, such as bioinformatics, machinelearning, big data analytics, and social networks. The success of the models has been basedon non-conventional, non-trivial graph metrics that can well characterize many applicationproblems and can lead to efficient graph optimization algorithms.