8 citations · 18 across the 8 of their papers we have counts for
8 papers · 1 filter
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…
Efficiently Realizing Interval Sequences
Amotz Bar-Noy, Keerti Choudhary, David Peleg +1
We consider the problem of realizable interval-sequences. An interval sequence comprises of integer intervals such that , and is said t…
Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods
Amotz Bar-Noy, Keerti Choudhary, David Peleg +1
The classical problem of degree sequence realizability asks whether or not a given sequence of positive integers is equal to the degree sequence of some -vertex undirected s…
Simple and Local Independent Set Approximation
Ravi B. Boppana, Magnús M. Halldórsson, Dror Rawitz
We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach o…
Maximizing Barrier Coverage Lifetime with Mobile Sensors
Amotz Bar-Noy, Dror Rawitz, Peter Terlecky
Sensor networks are ubiquitously used for detection and tracking and as a result covering is one of the main tasks of such networks. We study the problem of maximizing the coverage…
Set It and Forget It: Approximating the Set Once Strip Cover Problem
Amotz Bar-Noy, Ben Baumer, Dror Rawitz
We consider the Set Once Strip Cover problem, in which n wireless sensors are deployed over a one-dimensional region. Each sensor has a fixed battery that drains in inverse proport…