Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00255 Centdian Computation in Cactus Graphs Boaz Ben-Moshe , Amit Dvir , Michael Segal , and Arie Tamir Vol. 16, no. 2, pp. 199-224, 2012. Regular paper Abstract This paper focuses on the centdian problem in a cactus network where a cactus network is a connected undirected graph, and any two simple cycles in the graph have at most one node in common. The cactus network has important applications for wireless sensor networks when a tree topology might not be applicable and for extensions to the ring architecture. The centdian criterion represents a convex combination of two QoS requirements: transport and delay. To the best of our knowledge, no efficient algorithm has yet been developed for constructing a centdian node in a cactus graph, either sequential or distributed. We first investigate the properties of the centdian node in a cycle graph, and then explore the behavior of the centdian node in a cactus graph. Finally, we present new efficient sequential and distributed algorithms for finding all centdian nodes in a cycle graph and a cactus graph.
|
Reviewed: December 2011. Accepted: December 2011. Final: January 2012. Reviewed: February 2011. Published: January 2012. Submitted: July 2010. Revised: December 2011. Revised: June 2011. Communicated by Gerhard Woeginger |
| Journal of Graph Algorithms and Applications |