{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:11:47Z","timestamp":1725664307510},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540591757"},{"type":"electronic","value":"9783540492207"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59175-3_97","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:04:38Z","timestamp":1330275878000},"page":"300-310","source":"Crossref","is-referenced-by-count":0,"title":["On the approximability of some maximum spanning tree problems"],"prefix":"10.1007","author":[{"given":"Giulia","family":"Galbiati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Morzenti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Maffioli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedyr, M.: Proof verification and hardness of approximation problems. Proc. 33-rd Ann. IEEE Symp. on Foundations of Computer Science (1992) 14\u201323","DOI":"10.1109\/SFCS.1992.267823"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0377-2217(80)90164-2","volume":"5","author":"P. Camerini","year":"1980","unstructured":"Camerini, P., Galbiati, G., and Maffioli, F.: Complexity of spanning tree problems: Part I. European Journal of Operational Research 5 (1980) 346\u2013352","journal-title":"European Journal of Operational Research"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0166-218X(83)90014-8","volume":"5","author":"P. Camerini","year":"1983","unstructured":"Camerini, P., Galbiati, G., and Maffioli, F.: On the complexity of finding multi-constrained spanning trees. Discrete Applied Mathematics 5 (1983) 39\u201350","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR4","first-page":"53","volume":"44","author":"P. Camerini","year":"1986","unstructured":"Camerini, P., Galbiati, G., and Maffioli, F.: The complexity of weighted multi-constrained spanning tree problems. Colloquia Mathematica Societatis Janos Bolyai 44 (1986) 53\u2013101","journal-title":"Colloquia Mathematica Societatis Janos Bolyai"},{"key":"21_CR5","first-page":"241","volume":"2","author":"P. Crescenzi","year":"1993","unstructured":"Crescenzi, P., Panconesi, A.: Completeness in approximation classes. Information and Computation 2 (1993) 241\u2013262","journal-title":"Information and Computation"},{"key":"21_CR6","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/BF01762131","volume":"3","author":"M.R. Fellows","year":"1988","unstructured":"Fellows, M.R., Friesen, D.K., and Langston, M.A.: On Finding Optimal and Near-Optimal Lineal Spanning Trees. Algorithmica 3 (1988) 549\u2013560","journal-title":"Algorithmica"},{"key":"21_CR7","unstructured":"Furer, M., Raghavachari, B.: Approximating the Minimum Degree Spanning Tree to within One from the Optimal Degree. Proc. of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (1992) 317\u2013324"},{"key":"21_CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0020-0190(94)90139-2","volume":"52","author":"G. Galbiati","year":"1994","unstructured":"Galbiati, G., Maffioli, F., and Morzenti, A.: A Short Note on The Approximability of The Maximum Leaves Spanning Tree Problem. Information Processing Letters 52 (1994) 45\u201349","journal-title":"Information Processing Letters"},{"key":"21_CR9","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S., Dhmoys, D.B., Tardos, E., and Williamson, D.P.: Improved Approximation Algorithms for Network Design Problems. Proc. of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994) 223\u2013232"},{"key":"21_CR10","unstructured":"Lu, Hsueh-I, and Ravi, R.: The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree. Proc. Allerton Conference (1992) 533\u2013542"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Karger, D., Motwani, R., and Rankumar, G.D.S.: On Approximating the Longest Path in a Graph. Proc. of the 3rd Workshop on Algorithms and Data Structures (Lectures Notes in Comput. Sci. vol. 709) Springer-Verlag (1993) 421\u2013432","DOI":"10.1007\/3-540-57155-8_267"},{"key":"21_CR12","unstructured":"Khuller, S., Raghavachari, B., and Young, N.: Balancing Minimum Spanning Trees and Shortes-Path Trees. Proc. of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (1993)"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Khuller, S., Raghavachari, B., and Young, N.: Low Degree Spanning Trees of Small Weight. Proc. 26th Annual Symp. on the Theory of Computing (STOC '94) (1994)","DOI":"10.1145\/195058.195212"},{"key":"21_CR14","unstructured":"Lov\u00e1sz, L.: Combinatorial Problems and Exercises. North-Holland (1979)"},{"key":"21_CR15","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., and Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. and Syst. Sci. 43 (1991) 425\u2013440","journal-title":"J. Comput. and Syst. Sci."},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., and Hunt, H.B., III: Many birds with one stone: multi-objective approximation algorithms. Proc. 25th Annual Symp. on The Theory of Computing (STOC '94) (1993) 438\u2013447","DOI":"10.1145\/167088.167209"},{"key":"21_CR17","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., and Ravi, S.S.: Spanning Trees Short or Small. Proc. of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (1994) 546\u2013555"}],"container-title":["Lecture Notes in Computer Science","LATIN '95: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59175-3_97.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:24:24Z","timestamp":1619573064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59175-3_97"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540591757","9783540492207"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-59175-3_97","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}