Source author record

Lusheng Wang

Lusheng Wang appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Engineering, Finance, and Science Genomics math.AP Networking and Internet Architecture

Catalog footprint

What is connected

5works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

An Approximation Algorithm for Maximum Internal Spanning Tree

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 maximized. MIST has possible applications in the design of cost-efficient communication networks and water supply networks and hence has been extensively studied in the literature. MIST is NP-hard and hence a number of polynomial-time approximation algorithms have been designed for MIST in the literature. The previously best polynomial-time approximation algorithm for MIST achieves a ratio of 3/4. In this paper, we first design a simpler algorithm that achieves the same ratio and the same time complexity as the previous best. We then refine the algorithm into a new approximation algorithm that achieves a better ratio (namely, 13/17) with the same time complexity. Our new algorithm explores much deeper structure of the problem than the previous best. The discovered structure may be used to design even better approximation or parameterized algorithms for the problem in the future.

preprint2016arXiv

Core-genome scaffold comparison reveals the prevalence that inversion events are associated with pairs of inverted repeats

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 for genome rearrangement events remain unclear. Lots of comparisons have been conducted among different species. To reveal the mechanisms for rearrangement events, comparison of different individuals/strains within the same species or genus (pan-genomes) is more helpful since they are much closer to each other. Results: We study the mechanism for inversion events via core-genome scaffold comparison of different strains within the same species. We focus on two kinds of bacteria, Pseudomonas aeruginosa and Escherichia coli, and investigate the inversion events among different strains of the same specie. We find an interesting phenomenon that long (larger than 10,000 bp) inversion regions are flanked by a pair of Inverted Repeats (IRs) (with lengths ranging from 385 bp to 27476 bp) which are often Insertion Sequences (ISs).This mechanism can also explain why the breakpoint reuses for inversion events happen. We study the prevalence of the phenomenon and find that it is a major mechanism for inversions. The other observation is that for different rearrangement events such as transposition and inverted block interchange, the two ends of the swapped regions are also associated with repeats so that after the rearrangement operations the two ends of the swapped regions remain unchanged. To our knowledge, this is the first time such a phenomenon is reported for transposition event.

preprint2014arXiv

To Achieve Maximal Throughputs in CSMA Wireless Networks Through Offered_load Control

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-combination (CGC), to describe the relationship between the offered-load and the output link throughputs of an unsaturated CSMA network. Based on CGC, we then formulate a linear optimization model to improve the aggregate link throughput through properly setting the occurrence probabilities of each sub-network, based on which we can obtain the optimal offered-load of each link. Simulation results bore out the accuracy of our CGC analysis and the maximal link throughputs can be closely achieved. Different from prior work in which CSMA protocol parameters are adaptively adjusted to achieve better performance, in this paper we propose to achieve maximal link throughputs by adjusting the rates of the traffic pumped into the source nodes of links, which runs in a software manner and is more practical to implement in real networks.

preprint2013arXiv

An approximation algorithm for the Bandpass-2 problem

The general Bandpass-$B$ problem is NP-hard and can be approximated by a reduction into the weighted $B$-set packing problem, with a worst case performance ratio of $O(B^2)$. When $B = 2$, a maximum weight matching gives a 2-approximation to the problem. In this paper, we call the Bandpass-2 problem simply the Bandpass problem. The Bandpass problem can be viewed as a variation of the maximum traveling salesman problem, in which the edge weights are dynamic rather than given at the front. We present a ${426}{227}$-approximation algorithm for the problem. Such an improved approximation is built on an intrinsic structural property proven for the optimal solution and several novel schemes to partition a $b$-matching into desired matchings.