Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00255
Centdian Computation in Cactus Graphs
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.
|
Submitted: July 2010.
Reviewed: February 2011.
Revised: June 2011.
Reviewed: December 2011.
Revised: December 2011.
Accepted: December 2011.
Final: January 2012.
Published: January 2012.
Communicated by
Gerhard J. Woeginger
|
Journal Supporters
|