Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
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…
cs.DS2022
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…