5 papers
Approximately covering vertices by order- or longer paths
Mingyang Gong, Zhi-Zhong Chen, Guohui Lin +1
This paper studies , which is to cover as many vertices as possible in a given graph by vertex-disjoint -paths (i.e., paths each with at least five verti…
Men Can't Always be Transformed into Mice: Decision Algorithms and Complexity for Sorting by Symmetric Reversals
Xin Tong, Yixiao Yu, Ziyi Fang +4
Sorting a permutation by reversals is a famous problem in genome rearrangements. Since 1997, quite some biological evidence were found that in many genomes the reversed regions are…
Core-genome scaffold comparison reveals the prevalence that inversion events are associated with pairs of inverted repeats
Dan Wang, Shuaicheng Li, Fei Guo +1
Motivation: Genome rearrangement plays an important role in evolutionary biology and has profound impacts on phenotype in organisms ranging from microbes to humans. The mechanisms…
An Approximation Algorithm for Maximum Internal Spanning Tree
Zhi-Zhong Chen, Youta Harada, Lusheng Wang
Given a graph G, the {\em maximum internal spanning tree problem} (MIST for short) asks for computing a spanning tree T of G such that the number of internal vertices in T is maxim…
To Achieve Maximal Throughputs in CSMA Wireless Networks Through Offered_load Control
Caihong Kai, Qi Zhang, Lusheng Wang
This paper studies how to achieve the maximal link throughputs in a CSMA wireless network through offered-load control. First, we propose an analytical model, contention-graph-comb…