{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T22:47:24Z","timestamp":1773960444495,"version":"3.50.1"},"reference-count":62,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2023,11,21]],"date-time":"2023-11-21T00:00:00Z","timestamp":1700524800000},"content-version":"vor","delay-in-days":324,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572537"],"award-info":[{"award-number":["61572537"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1501252"],"award-info":[{"award-number":["U1501252"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["International Journal of Intelligent Systems"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p>The computation of a group Steiner tree (GST) in various types of graph networks, such as social network and transportation network, is a fundamental graph problem in graphs, with important applications. In these graphs, time is a common and necessary dimension, for example, time information in social network can be the time when a user sends a message to another user. Graphs with time information can be called temporal graphs. However, few studies have been conducted on GST in terms of temporal graphs. This study analyzes the computation of GST for temporal graphs, i.e., the computation of temporal GST (TGST), which is shown to be an NP\u2010hard problem. We propose an efficient solution based on a dynamic programming algorithm for our problem. This study adopts new optimization techniques, including graph simplification, state pruning, and <jats:italic>A<\/jats:italic><jats:sup>\u2217<\/jats:sup> search, are adopted to dramatically reduce the algorithm search space. Moreover, we consider three extensions for our problem, namely the TGST with unspecified tree root, the progressive search of TGST, and the top\u2010<jats:italic>N<\/jats:italic> search of TGST. Results of the experimental study performed on real temporal networks verify the efficiency and effectiveness of our algorithms.<\/jats:p>","DOI":"10.1155\/2023\/1974161","type":"journal-article","created":{"date-parts":[[2023,11,21]],"date-time":"2023-11-21T22:20:06Z","timestamp":1700605206000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Efficient Dynamic Programming Algorithm for Finding Group Steiner Trees in Temporal Graphs"],"prefix":"10.1155","volume":"2023","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5995-3242","authenticated-orcid":false,"given":"Youming","family":"Ge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6054-2782","authenticated-orcid":false,"given":"Zitong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0578-2956","authenticated-orcid":false,"given":"Weiyang","family":"Kong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2589-5168","authenticated-orcid":false,"given":"Yubao","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7045-6503","authenticated-orcid":false,"given":"Raymond Chi-Wing","family":"Wong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6685-9745","authenticated-orcid":false,"given":"Sen","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2023,11,21]]},"reference":[{"key":"e_1_2_13_1_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2012.03.001"},{"key":"e_1_2_13_2_2","doi-asserted-by":"crossref","unstructured":"WangS. LinW. YangY. XiaoX. andZhouS. Efficient route planning on public transportation networks: a labelling approach Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data May 2015 Melbourne Australia 967\u2013982.","DOI":"10.1145\/2723372.2749456"},{"key":"e_1_2_13_3_2","doi-asserted-by":"crossref","unstructured":"HuangS. FuA. W. C. andLiuR. Minimum spanning trees in temporal graphs Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data May 2015 Melbourne Australia 419\u2013430.","DOI":"10.1145\/2723372.2723717"},{"key":"e_1_2_13_4_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_13_5_2","doi-asserted-by":"crossref","unstructured":"RozenshteinP. GionisA. PrakashB. A. andVreekenJ. Reconstructing an epidemic over time Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining August 2016 San Francisco CA USA 1835\u20131844.","DOI":"10.1145\/2939672.2939865"},{"key":"e_1_2_13_6_2","doi-asserted-by":"crossref","unstructured":"XiaoH. RozenshteinP. TattiN. andGionisA. Reconstructing a cascade from temporal observations Proceedings of the 2018 SIAM International Conference on Data Mining October 2018 San Diego CA USA 666\u2013674.","DOI":"10.1137\/1.9781611975321.75"},{"key":"e_1_2_13_7_2","doi-asserted-by":"crossref","unstructured":"MaS. HuR. WangL. LinX. andHuaiJ. Fast computation of dense temporal subgraphs Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering April 2017 San Diego CA USA 361\u2013372.","DOI":"10.1109\/ICDE.2017.95"},{"key":"e_1_2_13_8_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137638"},{"key":"e_1_2_13_9_2","doi-asserted-by":"crossref","unstructured":"IkutaT.andAkibaT. Integer programming approach for directed minimum spanning tree problem on temporal graphs Proceedings of the 1st ACM SIGMOD Workshop on Network Data Analytics July 2016 San Francisco CA USA.","DOI":"10.1145\/2980523.2980528"},{"key":"e_1_2_13_10_2","doi-asserted-by":"crossref","unstructured":"QinH. LiR. H. WangG. QinL. ChengY. andYuanY. Mining periodic cliques in temporal networks Proceedings of the 2019 IEEE 35th International Conference on Data Engineering April 2019 Macao China 1130\u20131141.","DOI":"10.1109\/ICDE.2019.00104"},{"key":"e_1_2_13_11_2","doi-asserted-by":"crossref","unstructured":"YuanY. LianX. WangG. ChenL. MaY. andWangY. Weight-constrained route planning over time-dependent graphs Proceedings of the 2019 IEEE 35th International Conference on Data Engineering April 2019 Macao China 914\u2013925.","DOI":"10.1109\/ICDE.2019.00086"},{"key":"e_1_2_13_12_2","doi-asserted-by":"crossref","unstructured":"WuH. HuangY. ChengJ. LiJ. andKeY. Reachability and time-based path queries in temporal graphs Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering May 2016 Helsinki Finland 145\u2013156.","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"e_1_2_13_13_2","doi-asserted-by":"crossref","unstructured":"YangY. YanD. WuH. ChengJ. ZhouS. andLuiJ. C. S. Diversified temporal subgraph pattern mining Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining August 2016 San Francisco CA USA 1965\u20131974.","DOI":"10.1145\/2939672.2939848"},{"key":"e_1_2_13_14_2","doi-asserted-by":"crossref","unstructured":"ReichG.andWidmayerP. Beyond steiner\u2019s problem: a VLSI oriented generalization Proceedings of the International Workshop on Graph-theoretic Concepts in Computer Science June 1989 Berlin Germany 196\u2013210.","DOI":"10.1007\/3-540-52292-1_14"},{"key":"e_1_2_13_15_2","doi-asserted-by":"crossref","unstructured":"BhalotiaG. HulgeriA. NakheC. ChakrabartiS. andSudarshanS. Keyword searching and browsing in databases using BANKS Proceedings of the 18th International Conference on Data Engineering August 2002 San Jose CA USA 431\u2013440.","DOI":"10.1109\/ICDE.2002.994756"},{"key":"e_1_2_13_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.07.010"},{"key":"e_1_2_13_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/tkde.2012.228"},{"key":"e_1_2_13_18_2","doi-asserted-by":"crossref","unstructured":"DingB. YuJ. X. WangS. QinL. ZhangX. andLinX. Finding top-k min-cost connected trees in databases Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering April 2007 Istanbul Turkey 836\u2013845.","DOI":"10.1109\/ICDE.2007.367929"},{"key":"e_1_2_13_19_2","doi-asserted-by":"crossref","unstructured":"LappasT. LiuK. andTerziE. Finding a team of experts in social networks Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining June 2009 New York NY USA 467\u2013476.","DOI":"10.1145\/1557019.1557074"},{"key":"e_1_2_13_20_2","doi-asserted-by":"crossref","unstructured":"LiR. H. QinL. YuJ. X. andMaoR. Efficient and progressive group steiner tree search Proceedings of the 2016 International Conference on Management of Data June 2016 San Francisco CA USA 91\u2013106.","DOI":"10.1145\/2882903.2915217"},{"key":"e_1_2_13_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_13_22_2","doi-asserted-by":"crossref","unstructured":"KempeD. KleinbergJ. andKumarA. Connectivity and inference problems for temporal networks Proceedings of the thirty-second annual ACM symposium on Theory of computing January 2000 Portland OR USA 504\u2013513.","DOI":"10.1145\/335305.335364"},{"key":"e_1_2_13_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74247-0_3"},{"key":"e_1_2_13_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf01386390"},{"key":"e_1_2_13_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/tssc.1968.300136"},{"key":"e_1_2_13_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3830"},{"key":"e_1_2_13_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(84)90003-1"},{"key":"e_1_2_13_28_2","unstructured":"GoldbergA. V.andHarrelsonC. Computing the shortest path: a search meets graph theory Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms April 2005 Mountain View CA USA 156\u2013165."},{"key":"e_1_2_13_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2021.09.040"},{"key":"e_1_2_13_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450982"},{"key":"e_1_2_13_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-021-00154-4"},{"key":"e_1_2_13_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565834"},{"key":"e_1_2_13_33_2","doi-asserted-by":"publisher","DOI":"10.1002\/int.22781"},{"key":"e_1_2_13_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/tbdata.2020.2975587"},{"key":"e_1_2_13_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/tcss.2019.2906925"},{"key":"e_1_2_13_36_2","doi-asserted-by":"crossref","unstructured":"GongW. ZhangX. ChenY. HeQ. BeheshtiA. XuX. YanC. andQiL. DAWAR: diversity-aware web APIs recommendation for mashup creation based on correlation graph Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval July 2022 Madrid Spain 395\u2013404.","DOI":"10.1145\/3477495.3531962"},{"key":"e_1_2_13_37_2","unstructured":"GongW. WuH. WangX. ZhangX. ChenY. JiaS. andKhosraviM. Diversity-aware web APIs assignment and recommendation for mashup creation with compatibility guarantee 2021 https:\/\/arxiv.org\/abs\/2107.10538v2."},{"key":"e_1_2_13_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/tii.2021.3133614"},{"key":"e_1_2_13_39_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2902"},{"key":"e_1_2_13_40_2","doi-asserted-by":"crossref","unstructured":"HeP. LiuL. YouD. ShenL. andChenZ. BAT: mining binary-API topic for multi-service application development Proceedings of the 2023 26th International Conference on Computer Supported Cooperative Work in Design May 2023 Rio de Janeiro Brazil 745\u2013750.","DOI":"10.1109\/CSCWD57460.2023.10152814"},{"key":"e_1_2_13_41_2","first-page":"5444","article-title":"A correlation graph based approach for personalized and compatible web APIs recommendation in mobile APP development","volume":"35","author":"Qi L.","year":"2023","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_13_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00675-4"},{"key":"e_1_2_13_43_2","doi-asserted-by":"crossref","unstructured":"MassriM. Mikl\u00f3sZ. Parv\u00e9dyP. R. andMeyeP. Clock-G: a temporal graph management system with space-efficient storage technique Proceedings of the 38th IEEE International Conference on Data Engineering ICDE 2022 May 2022 Kuala Lumpur Malaysia 2263\u20132276.","DOI":"10.1109\/ICDE53745.2022.00215"},{"key":"e_1_2_13_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0499-4"},{"key":"e_1_2_13_45_2","doi-asserted-by":"crossref","unstructured":"LiL. WangS. andZhouX. Time-dependent hop labeling on road network Proceedings of the 35th IEEE International Conference on Data Engineering ICDE 2019 April 2019 Macao China 902\u2013913.","DOI":"10.1109\/ICDE.2019.00085"},{"key":"e_1_2_13_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2981062"},{"key":"e_1_2_13_47_2","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551856"},{"key":"e_1_2_13_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/tsmc.2021.3071721"},{"key":"e_1_2_13_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/tbdata.2021.3058294"},{"key":"e_1_2_13_50_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjds\/s13688-023-00379-5"},{"key":"e_1_2_13_51_2","doi-asserted-by":"crossref","unstructured":"JiangM. FuA. W. C. andWongR. C. W. Exact top-k nearest keyword search in large networks Proceedings of the 2015 ACM SIGMOD international conference on management of data May 2015 Melbourne Australia 393\u2013404.","DOI":"10.1145\/2723372.2749447"},{"key":"e_1_2_13_52_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350234"},{"key":"e_1_2_13_53_2","doi-asserted-by":"publisher","DOI":"10.1002\/int.21921"},{"key":"e_1_2_13_54_2","doi-asserted-by":"publisher","DOI":"10.1002\/int.22365"},{"key":"e_1_2_13_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-022-01748-8"},{"key":"e_1_2_13_56_2","doi-asserted-by":"crossref","unstructured":"FanW. HuC. andTianC. Incremental graph computations: doable and undoable Proceedings of the 2017 ACM International Conference on Management of Data May 2017 Chicago IL USA 155\u2013169.","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_2_13_57_2","doi-asserted-by":"crossref","unstructured":"WuH. ZhaoY. ChengJ. andYanD. Efficient processing of growing temporal graphs Proceedings of the Database Systems for Advanced Applications: 22nd International Conference March 2017 Berlin Germany 387\u2013403.","DOI":"10.1007\/978-3-319-55699-4_24"},{"key":"e_1_2_13_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.755613"},{"key":"e_1_2_13_59_2","doi-asserted-by":"publisher","DOI":"10.1002\/int.22927"},{"key":"e_1_2_13_60_2","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598592"},{"key":"e_1_2_13_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3589315"},{"key":"e_1_2_13_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-023-00218-7"}],"container-title":["International Journal of Intelligent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/ijis\/2023\/1974161.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/ijis\/2023\/1974161.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2023\/1974161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,31]],"date-time":"2024-12-31T05:10:40Z","timestamp":1735621840000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2023\/1974161"}},"subtitle":[],"editor":[{"given":"Lianyong","family":"Qi","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.1155\/2023\/1974161"],"URL":"https:\/\/doi.org\/10.1155\/2023\/1974161","archive":["Portico"],"relation":{},"ISSN":["0884-8173","1098-111X"],"issn-type":[{"value":"0884-8173","type":"print"},{"value":"1098-111X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"2022-11-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-31","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"1974161"}}