{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:01:17Z","timestamp":1725534077748},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642022692"},{"type":"electronic","value":"9783642022708"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02270-8_30","type":"book-chapter","created":{"date-parts":[[2009,6,19]],"date-time":"2009-06-19T05:17:47Z","timestamp":1245388667000},"page":"293-301","source":"Crossref","is-referenced-by-count":4,"title":["Approximating the Spanning k-Tree Forest Problem"],"prefix":"10.1007","author":[{"given":"Chung-Shou","family":"Liao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","unstructured":"Bock, F.: An algorithm to construct a minimum directed spanning tree in a directed network. In: Developments in Operations Research, pp. 29\u201344. Gordon and Breach, New York (1971)"},{"key":"30_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/net.3230090403","volume":"9","author":"P.M. Camerini","year":"1979","unstructured":"Camerini, P.M., Fratta, L., Maffioli, F.: A note on finding optimum branchings. Networks\u00a09, 309\u2013312 (1979)","journal-title":"Networks"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Goel, G.: On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. In: Proceedings of the 49th IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 687\u2013696 (2008)","DOI":"10.1109\/FOCS.2008.47"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Chang, G.J.: Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Appl. Math.\u00a022, 21\u201334 (1988\/1989)","DOI":"10.1016\/0166-218X(88)90120-5"},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-74208-1_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N. Chen","year":"2007","unstructured":"Chen, N., Engelberg, R., Nguyen, C.T., Raghavendra, P., Rudra, A., Singh, G.: Improved approximation algorithms for the spanning star forest problem. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 44\u201358. Springer, Heidelberg (2007)"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","volume":"4","author":"E.J. Cockayne","year":"1975","unstructured":"Cockayne, E.J., Goodman, S.E., Hedetniemi, S.T.: A linear algorithm for the domination number of a tree. Inform. Process. Lett.\u00a04, 41\u201344 (1975)","journal-title":"Inform. Process. Lett."},{"key":"30_CR7","first-page":"1396","volume":"14","author":"Y.J. Chu","year":"1965","unstructured":"Chu, Y.J., Liu, T.H.: On the shortest arborescence of a directed graph. Science Sinica\u00a014, 1396\u20131400 (1965)","journal-title":"Science Sinica"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Research of the National Bureau of Standards\u00a071B, 233\u2013240 (1967)","journal-title":"J. Research of the National Bureau of Standards"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM\u00a048, 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"30_CR10","volume-title":"Domination in Graphs: Advanced Topics","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Marcel Dekker, Inc., New York (1998)"},{"key":"30_CR11","first-page":"11","volume":"16","author":"M.A. Henning","year":"1991","unstructured":"Henning, M.A., Oellermann, O.R., Swart, H.C.: Bounds on distance domination parameters. J. Combin. Inform. System. Sci.\u00a016, 11\u201318 (1991)","journal-title":"J. Combin. Inform. System. Sci."},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0012-365X(95)00074-7","volume":"161","author":"M.A. Henning","year":"1996","unstructured":"Henning, M.A., Oellermann, O.R., Swart, H.C.: The diversity of domination. Discrete Math.\u00a0161, 161\u2013173 (1996)","journal-title":"Discrete Math."},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM\u00a032, 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/net.3230010305","volume":"1","author":"R.M. Karp","year":"1971","unstructured":"Karp, R.M.: A simple derivation of edmonds\u2019 algorithm for optimum branchings. Networks\u00a01, 265\u2013272 (1971)","journal-title":"Networks"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0020-0190(03)00233-3","volume":"87","author":"C.S. Liao","year":"2003","unstructured":"Liao, C.S., Chang, G.J.: k-tuple domination in graphs. Inform. Process. Lett.\u00a087, 45\u201350 (2003)","journal-title":"Inform. Process. Lett."},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Nguyen, C.T., Shen, J., Hou, M., Sheng, L., Miller, W., Zhang, L.: Approximating the spanning star forest problem and its applications to genomic sequence alignment. SIAM J. Comput.\u00a038, 946\u2013962 (2008); also appeared in Proc. of SODA 2007, pp. 645\u2013654 (2007)","DOI":"10.1137\/070682150"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R.E. Tarjan","year":"1977","unstructured":"Tarjan, R.E.: Finding optimum branchings. Networks\u00a07, 25\u201335 (1977)","journal-title":"Networks"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1145\/321958.321964","volume":"23","author":"P.J. Slater","year":"1976","unstructured":"Slater, P.J.: R-Domination in Graphs. J. ACM\u00a023, 446\u2013450 (1976)","journal-title":"J. ACM"},{"key":"30_CR19","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math.\u00a038, 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02270-8_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:09:26Z","timestamp":1558397366000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02270-8_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022692","9783642022708"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02270-8_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}