{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T17:12:07Z","timestamp":1712423527804},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,5,24]],"date-time":"2012-05-24T00:00:00Z","timestamp":1337817600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2013,2]]},"DOI":"10.1007\/s10878-012-9499-2","type":"journal-article","created":{"date-parts":[[2012,5,23]],"date-time":"2012-05-23T14:56:27Z","timestamp":1337784987000},"page":"255-264","source":"Crossref","is-referenced-by-count":3,"title":["Improved approximation for spanning star forest in dense graphs"],"prefix":"10.1007","volume":"25","author":[{"given":"Jing","family":"He","sequence":"first","affiliation":[]},{"given":"Hongyu","family":"Liang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,24]]},"reference":[{"key":"9499_CR1","first-page":"XVII","volume-title":"Proceedings of the 17th European conference on combinatorial optimization (ECCO)","author":"A Agra","year":"2005","unstructured":"Agra A, Cardoso D, Cerfeira O, Rocha E (2005) A spanning star forest model for the diversity problem in automobile industry. In: Proceedings of the 17th European conference on combinatorial optimization (ECCO), p XVII"},{"issue":"1","key":"9499_CR2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1006\/jcss.1998.1605","volume":"58","author":"S Arora","year":"1999","unstructured":"Arora S, Karger D, Karpinski M (1999) Polynomial time approximation schemes for dense instances of NP-hard problems. J Comput Syst Sci 58(1):193\u2013210","journal-title":"J Comput Syst Sci"},{"key":"9499_CR3","series-title":"LNCS","first-page":"90","volume-title":"34th international symposium on mathematical foundations of computer science (MFCS)","author":"S Athanassopoulos","year":"2009","unstructured":"Athanassopoulos S, Caragiannis I, Kaklamanis C, Kuropoulou M (2009) An improved approximation bound for spanning star forest and color saving. In: 34th international symposium on mathematical foundations of computer science (MFCS). LNCS, vol 5734, pp 90\u2013101"},{"key":"9499_CR4","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/11533719_14","volume-title":"11th international computing and combinatorics conference (COCOON)","author":"V Berry","year":"2005","unstructured":"Berry V, Guillemot S, Nicholas F, Paul C (2005) On the approximation of computing evolutionary trees. In: 11th international computing and combinatorics conference (COCOON). LNCS, vol 3595, pp\u00a0115\u2013125"},{"key":"9499_CR5","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1016\/j.tcs.2008.12.036","volume":"410","author":"J Cardinal","year":"2009","unstructured":"Cardinal J, Langerman S, Levy E (2009) Improved approximation bounds for edge dominating set in dense graphs. Theor Comput Sci 410:949\u2013957","journal-title":"Theor Comput Sci"},{"key":"9499_CR6","unstructured":"Cardinal J, Karpinski M, Schmied R, Viehmann C (2010) Approximating subdense instances of covering problems. arXiv: 1011.0078v2"},{"key":"9499_CR7","first-page":"687","volume-title":"Proceedings of 49th annual IEEE symposium on foundations of computer science (FOCS)","author":"D Chakrabarty","year":"2008","unstructured":"Chakrabarty D, Goel G (2008) On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and gap. In: Proceedings of 49th annual IEEE symposium on foundations of computer science (FOCS), pp 687\u2013696"},{"key":"9499_CR8","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/978-3-540-74208-1_4","volume-title":"10th intl workshop on approximation algorithms for combinatorial optimization problems (APPROX)","author":"N Chen","year":"2007","unstructured":"Chen N, Engelberg R, Nguyen CT, Raghavendra P, Rudra A, Singh G (2007) Improved approximation algorithms for the spanning star forest problem. In: 10th intl workshop on approximation algorithms for combinatorial optimization problems (APPROX). LNCS, vol 4627, pp 44\u201358"},{"key":"9499_CR9","first-page":"256","volume-title":"Proceedings of the 29th annual ACM symposium on the theory of computing (STOC)","author":"R Duh","year":"1997","unstructured":"Duh R, Furer M (1997) Approximation of k-set cover by semi local optimization. In: Proceedings of the 29th annual ACM symposium on the theory of computing (STOC), pp 256\u2013264"},{"issue":"4","key":"9499_CR10","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of lnn for approximating set cover. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"key":"9499_CR11","doi-asserted-by":"crossref","unstructured":"Gaspers S, Kratsch D, Liedloff M, Todinca I (2009) Exponential time algorithms for the minimum dominating set problem on some graph classes. ACM Trans Algorithms\u00a06(1)","DOI":"10.1145\/1644015.1644024"},{"key":"9499_CR12","first-page":"582","volume-title":"Proceedings of the 16th annual ACM-SIAM symposium on discrete algorithms (SODA)","author":"T Imamura","year":"2005","unstructured":"Imamura T, Iwama K (2005) Approximating vertex cover on dense graphs. In: Proceedings of the 16th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 582\u2013589"},{"issue":"3","key":"9499_CR13","doi-asserted-by":"crossref","first-page":"946","DOI":"10.1137\/070682150","volume":"38","author":"CT Nguyen","year":"2008","unstructured":"Nguyen CT, Shen J, Hou M, Sheng L, Miller W, Zhang L (2008) Approximating the spanning star forest problem and its applications to genomic sequence alignment. SIAM J Comput 38(3):946\u2013962","journal-title":"SIAM J Comput"},{"key":"9499_CR14","first-page":"475","volume-title":"Proceedings of the 29th annual ACM symposium on the theory of computing (STOC)","author":"R Raz","year":"1997","unstructured":"Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th annual ACM symposium on the theory of computing (STOC), pp 475\u2013484"},{"key":"9499_CR15","doi-asserted-by":"crossref","first-page":"33","DOI":"10.7151\/dmgt.1004","volume":"15","author":"I Schiermeyer","year":"1995","unstructured":"Schiermeyer I (1995) Problems remaining NP-complete for sparse or dense graphs. Discuss Math Graph Theory 15:33\u201341","journal-title":"Discuss Math Graph Theory"},{"key":"9499_CR16","volume-title":"Approximation algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani V (2001) Approximation algorithms. Springer, Berlin"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9499-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-012-9499-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9499-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:23:18Z","timestamp":1559262198000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-012-9499-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,24]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["9499"],"URL":"https:\/\/doi.org\/10.1007\/s10878-012-9499-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,24]]}}}