An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization

We give an O(^k · n²) fixed parameter tractable algorithm for the 1-Sided Crossing Minimization. The constant in the running time is the golden ratio = (1+5)/2 1.618. The constant k is the parameter of the problem: the number of allowed edge crossings.     

顶点覆盖变体问题的确定参数可解算法研究

参数复杂性作为算法研究的一个重要分支,近十年来在国际上受到了广泛的关注,确定参数可解算法是参数复杂性研究的一类重要问题,因此被广泛研究。本文主要研究了顶点覆盖问题的两个变体问题：一个是连接的顶点覆盖问题,二是含权的树型顶点覆盖问题。这两个问题都是对原始的顶点覆盖问题加入了一些限制的变体问题。本文给出了这两个问题的确定参数可解算法,并且是目前的最好结果。     

Encoding and Constructing 1-Nested Phylogenetic Networks with Trinets

Phylogenetic networks are a generalization of phylogenetic trees that are used in biology to represent reticulate or non-treelike evolution. Recently, several algorithms have been developed which aim to construct phylogenetic networks from biological data using triplets, i.e. binary phylogenetic trees on 3-element subsets of a given set of species. However, a fundamental problem with this approach is that the triplets displayed by a phylogenetic network do not necessarily uniquely determine or encode the network. Here we propose an alternative approach to encoding and constructing phylogenetic networks, which uses phylogenetic networks on 3-element subsets of a set, or trinets, rather than triplets. More specifically, we show that for a special, well-studied type of phylogenetic network called a 1-nested network, the trinets displayed by a 1-nested network always encode the network. We also present an efficient algorithm for deciding whether a dense set of trinets (i.e. one that contains a trinet on every 3-element subset of a set) can be displayed by a 1-nested network or not and, if so, constructs that network. In addition, we discuss some potential new directions that this new approach opens up for constructing and comparing phylogenetic networks.     

Constructing the Simplest Possible Phylogenetic Network from Triplets

A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing so-called reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network with smallest possible level in time O(|T| ^k+1), if k is a fixed upper bound on the level of the network.     

从信息学的角度分析复杂网络链路预测

链路预测作为复杂网络分析的一项重要任务,其目的是寻找节点间缺失(新)的链路,识别虚假交互,对于挖掘和分析网络的演化,重塑网络模型具有重要意义.传统的链路预测方法多数采用拓扑结构信息、节点的属性信息和图的结构特征.应用这些特征等外部信息可以得到很好的预测效果.本文从信息学的角度全面分析、回顾和讨论了复杂网络链路预测的发展现状,提出了链路预测技术和问题的系统分类.首次将分层的思想引入链路预测分类体系中,把当前的链路预测方法分为基于监督学习的技术、基于半监督学习的技术、基于无监督学习的技术和基于强化学习的技术.对每种技术的优缺点、复杂性、所使用的具体特征,开源实现及应用建议进行了详细的分析.最后,讨论了当前复杂网络链路预测技术未来的发展方向.