Search Results - Springer

Chapter and Conference Paper

Morelia Test: Improving the Efficiency of the Gabriel Test and Face Routing in Ad-Hoc Networks

An important technique for discovering routes between two nodes in an ad-hoc network involves applying the face routing algorithm on a planar spanner of the network. Face routing guarantees message delivery in...

Paul Boone, Edgar Chavez, Lev Gleitzky… in Structural Information and Communication C… (2004)

Chapter and Conference Paper

Two-Hop Virtual Path Layout in Tori

We consider the problem of D-hop virtual path layout in ATM (Asynchronous Transfer Mode) networks. Given a physical network and an all-to-all traffic pattern, the problem consists of designing a virtual network w...

Sébastien Choplin, Lata Narayanan… in Structural Information and Communication C… (2004)

Chapter and Conference Paper

Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges

We give an algorithm for constructing a connected spanning subgraphs(panner) of a wireless network modelled as a unit disk graph with nodes of irregular transmission ranges, whereby for some parameter 0 < r ≤ 1 t...

Edgar Chávez, Stefan Dobrev, Evangelos Kranakis… in LATIN 2006: Theoretical Informatics (2006)

Chapter and Conference Paper

Local Edge Colouring of Yao-Like Subgraphs of Unit Disk Graphs

The focus of the present paper is on providing a local deterministic algorithm for colouring the edges of Yao-like subgraphs of Unit Disc Graphs. These are geometric graphs such that for some positive integers l,

Jurek Czyzowicz, Stefan Dobrev… in Structural Information and Communication C… (2007)

Chapter and Conference Paper

Optimal Sensor Networks for Area Monitoring Using Rotating and Beam Sensors

We consider the problem of monitoring the Euclidean plane using rotating sensors with detection sectors and beam sensors. We assume that intruders can appear anywhere at any time and move arbitrarily fast, and...

Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny in Fun with Algorithms (2012)

Chapter and Conference Paper

Complexity of Barrier Coverage with Relocatable Sensors in the Plane

We consider several variations of the problems of covering a set of barriers (modeled as line segments) using sensors that can detect any intruder crossing any of the barriers. Sensors are initially located in...

Stefan Dobrev, Stephane Durocher, Mohsen Eftekhari… in Algorithms and Complexity (2013)

Chapter and Conference Paper

Distributed Barrier Coverage with Relocatable Sensors

A wireless sensor can detect the presence of an intruder in its sensing range, and is said to cover the portion of a given barrier that intersects with its sensing range. Barrier coverage is achieved by a set ...

Mohsen Eftekhari, Paola Flocchini… in Structural Information and Communication C… (2014)

Chapter and Conference Paper

Linear Search with Terrain-Dependent Speeds

We revisit the linear search problem where a robot, initially placed at the origin on an infinite line, tries to locate a stationary target placed at an unknown position on the line. Unlike previous studies, in w...

Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc… in Algorithms and Complexity (2017)

Chapter and Conference Paper

Weak Coverage of a Rectangular Barrier

Assume n wireless mobile sensors are initially dispersed in an ad hoc manner in a rectangular region. They are required to move to final locations so that they can detect any intruder crossing the region in a dir...

Stefan Dobrev, Evangelos Kranakis, Danny Krizanc… in Algorithms and Complexity (2017)

Chapter and Conference Paper

Satisfying Neighbor Preferences on a Circle

We study the problem of satisfying seating preferences on a circle. We assume we are given a collection of n agents to be arranged on a circle. Each agent is colored either blue or red, and there are exactly b bl...

Danny Krizanc, Manuel Lafond, Lata Narayanan… in LATIN 2018: Theoretical Informatics (2018)