A Self‐stabilizing Algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives

A Self‐stabilizing Algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives

0.00 Avg rating0 Votes
Article ID: iaor2012386
Volume: 62
Issue: 1
Start Page Number: 146
End Page Number: 168
Publication Date: Feb 2012
Journal: Algorithmica
Authors: , , ,
Keywords: trees
Abstract:

Given a graph G=(V,E), a vertex v of G is a median vertex if it minimizes the sum of the distances to all other vertices of G. The median problem consists of finding the set of all median vertices of G. In this note, we present self‐stabilizing algorithms for the median problem in partial rectangular grids and relatives. Our algorithms are based on the fact that partial rectangular grids can be isometrically embedded into the Cartesian product of two trees, to which we apply the algorithm proposed by Antonoiu and Srimani (1999) and Bruell et al. (1999) for computing the medians in trees. Then we extend our approach from partial rectangular grids to a more general class of plane quadrangulations. We also show that the characterization of medians of trees given by Gerstel and Zaks (1994) extends to cube‐free median graphs, a class of graphs which includes these quadrangulations.

Reviews

Required fields are marked *. Your email address will not be published.