{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:40:14Z","timestamp":1767339614072},"reference-count":4,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p> A star is a graph in which some node is incident with every edge of the graph, i.e., a graph of diameter at most 2. A star forest is a graph in which each connected component is a star. Given a connected graph G in which the edges may be weighted positively. A spanning star forest of G is a subgraph of G which is a star forest spanning the nodes of G. The size of a spanning star forest F of G is defined to be the number of edges of F if G is unweighted and the total weight of all edges of F if G is weighted. We are interested in the problem of finding a Maximum Weight spanning Star Forest (MWSFP) in G. In [C. T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller and L. Zhang, Approximating the spanning star forest problem and its applications to genomic sequence alignment, SIAM J. Comput.\u00a038(3) (2008) 946\u2013962], the authors introduced the MWSFP and proved its NP-hardness. They also gave a polynomial time algorithm for the MWSF problem when G is a tree. In this paper, we present a linear time algorithm that solves the MSWF problem when G is a cactus. <\/jats:p>","DOI":"10.1142\/s1793830915500184","type":"journal-article","created":{"date-parts":[[2015,3,23]],"date-time":"2015-03-23T01:43:24Z","timestamp":1427075004000},"page":"1550018","source":"Crossref","is-referenced-by-count":5,"title":["The maximum weight spanning star forest problem on cactus graphs"],"prefix":"10.1142","volume":"07","author":[{"given":"Viet Hung","family":"Nguyen","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9s, UPMC Univ Paris 06, UMR 7606, LIP6, 4 Place Jussieu, Paris, France"}]}],"member":"219","published-online":{"date-parts":[[2015,5,25]]},"reference":[{"key":"rf2","doi-asserted-by":"crossref","unstructured":"S.\u00a0Athanassopoulos, Mathematical Foundation of Computer Science (Springer, 2009)\u00a0pp. 90\u2013101.","DOI":"10.1007\/978-3-642-03816-7_9"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21204-8_11"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/070682150"},{"key":"rf8","volume-title":"Introduction to Graph Theory","author":"West D.","year":"2000"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830915500184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T03:36:10Z","timestamp":1565148970000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830915500184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,25]]},"references-count":4,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2015,5,25]]},"published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1142\/S1793830915500184"],"URL":"https:\/\/doi.org\/10.1142\/s1793830915500184","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,25]]}}}