Kien Trung Nguyen, Van Chien, Pham, Ly Hong Hai, and Huynh Duc Quoc
Subjects
*LINEAR systems, *GRAPH theory, *ALGORITHMS, *TREE graphs, *LINEAR time invariant systems
Abstract
We address the problem of finding a 1-median on a cactus graph. The problem has already been solved in linear time by the algorithms of Burkard and Krarup (1998), and Lan and Wang (2000). These algorithms are complicated and need efforts. Hence, we develop in this paper a simpler algorithm. First, we construct a condition for a cycle that contains a 1-median or for a vertex that is indeed a 1-median of the cactus. Based on this condition, we localize the search for deriving a 1-median on the underlying cactus. Complexity analysis shows that the approach runs in linear time. [ABSTRACT FROM AUTHOR]
Published
2017
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.