{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:27:11Z","timestamp":1725560831289},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540210795"},{"type":"electronic","value":"9783540245926"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24592-6_12","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T03:13:33Z","timestamp":1280373213000},"page":"151-164","source":"Crossref","is-referenced-by-count":3,"title":["On the Approximability of the Minimum Fundamental Cycle Basis Problem"],"prefix":"10.1007","author":[{"given":"Giulia","family":"Galbiati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edoardo","family":"Amaldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. Journal of ACM\u00a045, 501\u2013555 (1998)","journal-title":"Journal of ACM"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"Alon, N., Karp, R., Peleg, D., West, D.: Graph-theoretic game and its application to the k-server problem. SIAM J. Comput.\u00a024, 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"key":"12_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and approximation: Combinatorial optimization problems and their approximability properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer, Heidelberg (1999)"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On the approximation of metric spaces by tree metrics. In: Proceedings of STOC 1998, pp. 161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"938","DOI":"10.1109\/81.940184","volume":"48","author":"A. Brambilla","year":"2001","unstructured":"Brambilla, A., Premoli, A.: Rigorous event-driven (RED) analysis of large scale RC circuits. IEEE Trans. on CAS-I\u00a048, 938\u2013954 (2001)","journal-title":"IEEE Trans. on CAS-I"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a finite metric by a small number of tree metrics. In: Proceedings of FOCS 1998, pp. 161\u2013168 (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/355984.355988","volume":"8","author":"N. Deo","year":"1982","unstructured":"Deo, N., Prabhu, G.M., Krishamoorthy, M.S.: Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Software\u00a08, 26\u201342 (1982)","journal-title":"ACM Trans. Math. Software"},{"key":"12_CR8","first-page":"141","volume":"107","author":"N. Deo","year":"1995","unstructured":"Deo, N., Kumar, N., Parsons, J.: Minimum-length fundamental-cycle set: New heuristics and an empirical study. Congressus Numerantium\u00a0107, 141\u2013154 (1995)","journal-title":"Congressus Numerantium"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximatinng arbitrary metrics by tree metrics. In: Proceedings of STOC 2003, pp. 448\u2013455 (2003)","DOI":"10.1145\/780542.780608"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/3-540-45678-3_11","volume-title":"Algorithms and Computation","author":"G. Galbiati","year":"2001","unstructured":"Galbiati, G.: On min-max cycle bases. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 116\u2013123. Springer, Heidelberg (2001)"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"J.D. Horton","year":"1987","unstructured":"Horton, J.D.: A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput.\u00a016, 358\u2013366 (1987)","journal-title":"SIAM J. Comput."},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1137\/0203015","volume":"3","author":"T.C. Hu","year":"1974","unstructured":"Hu, T.C.: Optimum communication spanning trees. SIAM J. Comput.\u00a03, 188\u2013195 (1974)","journal-title":"SIAM J. Comput."},{"key":"12_CR13","unstructured":"Liebchen, C., Peeters, L.: On cyclic timetabling and cycles in graphs. Technical Report 761, Technische Universit\u00e4t Berlin (2002)"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0020-0190(01)00161-2","volume":"80","author":"G. Konjevod","year":"2001","unstructured":"Konjevod, G., Ravi, R., Salman, F.S.: On approximating planar metrics by tree metrics. Information Processing Letters\u00a080, 213\u2013219 (2001)","journal-title":"Information Processing Letters"},{"key":"12_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System Sci.\u00a043, 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"key":"12_CR16","unstructured":"Peleg, D.: Polylogarithmic approximation for minimum communication spanning trees. Technical Report CS 97-10, The Weizmann Institute (July 1997)"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/3-540-45687-2_5","volume-title":"Mathematical Foundations of Computer Science 2002","author":"D. Peleg","year":"2002","unstructured":"Peleg, D.: Low stretch spanning trees. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 68\u201380. Springer, Heidelberg (2002)"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1007\/BFb0055092","volume-title":"Automata, Languages and Programming","author":"D. Peleg","year":"1998","unstructured":"Peleg, D., Reshef, E.: Deterministic polylog approximation for minimum communication spanning trees. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 670\u2013681. Springer, Heidelberg (1998)"},{"key":"12_CR19","unstructured":"Reshef, E.: Approximating minimum communication cost spanning trees and related problems. M.Sc. Thesis, The Weizmann Institute of Science (1999)"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/net.3230090203","volume":"9","author":"M.M. Syslo","year":"1979","unstructured":"Syslo, M.M.: On cycle bases of a graph. Networks\u00a09, 123\u2013132 (1979)","journal-title":"Networks"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1021\/c160016a007","volume":"5","author":"E. Sussenouth Jr.","year":"1965","unstructured":"Sussenouth Jr., E.: A graph theoretical algorithm for matching chemical structures. J. Chem. Doc.\u00a05, 36\u201343 (1965)","journal-title":"J. Chem. Doc."},{"key":"12_CR22","unstructured":"Vismara, P.: Reconnaissance et repr\u00e9sentation d\u2019\u00e9l\u00e9ments structuraux pour la description d\u2019objets complexes. Application \u00e0 l\u2019\u00e9laboration de strat\u00e9gies de synth\u00e8se en chimie organique. Th\u00e8se de Doctorat, Universit\u00e9 de Montpellier II, France (1995)"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1137\/S009753979732253X","volume":"29","author":"B.Y. Wu","year":"1999","unstructured":"Wu, B.Y., Lancia, G., Bafna, V., Chao, K.-M., Ravi, R., Tang, C.Y.: A polynomialtime approximation scheme for minimum routing cost spanning trees. SIAM J. Comput.\u00a029, 761\u2013778 (1999)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24592-6_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:38:04Z","timestamp":1559331484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24592-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540210795","9783540245926"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24592-6_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}