Linear algorithms on Steiner domination of trees

2019/04/14 by Yueming Shen, Chengye Zhao, Shen, Yueming +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1904.06785

arxiv created 2020/02/28 · arxiv updated 2020/03/02

Abstract

A set of vertices W in a connected graph G is called a Steiner dominating set if W is both Steiner and dominating set. The Steiner domination number γ_st(G) is the minimum cardinality of a Steiner dominating set of G. A linear algorithm is proposed in this paper for finding a minimum Steiner dominating set for a tree T.

Related

• Hardness Results and Approximation Algorithms for the Minimum Dominating Tree Problem
• Tree Decomposition based Steiner Tree Computation over Large Graphs
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Optimal algorithm for computing Steiner 3-eccentricities of trees
• Minimal Dominating Sets in a Tree: Counting, Enumeration, and Extremal Results