2018/11/29 by Yahui Sun, Sun, Yahui
Psychology · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Innovative Teaching and Learning Methods
paper · pdf · doi:10.48550/arxiv.1812.01678
openalex publication_date 2018/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Steiner tree problems are well-known NP-hard problems that have diverse applications. Duin et al. (2004) have intuitively proposed the widely-used transformation from the classical group Steiner tree problem to the classical Steiner tree problem in graphs. This transformation has not been rigorously proven so far. Specifically, the large M value that is used in this transformation has not been specified. In this paper, we address this issue by rigorously prove this transformation for a specific large M value.