19 citations · 19 across the 7 of their papers we have counts for
8 papers
Degree Realization by Bipartite Cactus Graphs
Amotz Bar-Noy, Toni Bohnlein, David Peleg +2
The \textsc{Degree Realization} problem with respect to a graph family is defined as follows. The input is a sequence of positive integers, and the goal is to…
Approximate Realizations for Outerplanaric Degree Sequences
Amotz Bar-Noy, Toni Bohnlein, David Peleg +2
We study the question of whether a sequence d = (d_1,d_2, \ldots, d_n) of positive integers is the degree sequence of some outerplanar (a.k.a. 1-page book embeddable) graph G. If s…
A New Approximation Algorithm for Minimum-Weight --Connected Dominating Set
Jiao Zhou, Yingli Ran, Panos M. Pardalos +3
Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset…
Approximation Algorithm for Minimum Union Under a Geometric Setting
Yingli Ran, Zhao Zhang
In a minimum union problem (MinU), given a hypergraph and an integer , the goal is to find a set of hyperedges such that the number of verti…
A parallel algorithm for minimum weight set cover with small neighborhood property
Yingli Ran, Yaoyao Zhang, Zhao Zhang
This paper studies the minimum weight set cover (MinWSC) problem with a {\em small neighborhood cover} (SNC) property proposed by Agarwal {\it et al.} in \cite{Agarwal.}. A paralle…
Performance Guaranteed Evolutionary Algorithm for Minimum Connected Dominating Set
Chaojie Zhu, Yingli Ran, Zhao Zhang +1
A connected dominating set is a widely adopted model for the virtual backbone of a wireless sensor network. In this paper, we design an evolutionary algorithm for the minimum conne…
Improved Parallel Algorithm for Minimum Cost Submodular Cover Problem
Yingli Ran, Zhao Zhang, Shaojie Tang
In the minimum cost submodular cover problem (MinSMC), we are given a monotone nondecreasing submodular function , a linear cost function $c:…
Approximation Algorithm for the Partial Set Multi-Cover Problem
Yishuo Shi, Yingli Ran, Zhao Zhang +3
Partial set cover problem and set multi-cover problem are two generalizations of set cover problem. In this paper, we consider the partial set multi-cover problem which is a combin…