{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T15:09:51Z","timestamp":1791212991448,"version":"4.1.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,1,14]],"date-time":"2011-01-14T00:00:00Z","timestamp":1294963200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s00454-010-9322-8","type":"journal-article","created":{"date-parts":[[2011,1,13]],"date-time":"2011-01-13T19:54:46Z","timestamp":1294948486000},"page":"425-448","source":"Crossref","is-referenced-by-count":35,"title":["Hardness Results for Homology Localization"],"prefix":"10.1007","volume":"45","author":[{"given":"Chao","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Freedman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,1,14]]},"reference":[{"issue":"3","key":"9322_CR1","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/1097-0037(200010)36:3<147::AID-NET1>3.0.CO;2-M","volume":"36","author":"E.M. Arkin","year":"2000","unstructured":"Arkin, E.M., Hassin, R.: Minimum-diameter covering problems. Networks 36(3), 147\u2013155 (2000)","journal-title":"Networks"},{"issue":"2","key":"9322_CR2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317\u2013331 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9322_CR3","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1016\/j.ejor.2005.06.006","volume":"172","author":"G. Ausiello","year":"2006","unstructured":"Ausiello, G., Paschos, V.T.: Reductions, completeness and the hardness of approximability. Eur. J. Oper. Res. 172(3), 719\u2013739 (2006)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"9322_CR4","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1142\/S021819590600204X","volume":"16","author":"E. Carlsson","year":"2006","unstructured":"Carlsson, E., Carlsson, G., de Silva, V.: An algebraic topological method for feature identification. Int. J. Comput. Geom. Appl. 16(4), 291\u2013314 (2006)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"9322_CR5","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1090\/S0273-0979-09-01249-X","volume":"46","author":"G. Carlsson","year":"2009","unstructured":"Carlsson, G.: Topology and data. Bull. Am. Math. Soc. 46(2), 255\u2013308 (2009)","journal-title":"Bull. Am. Math. Soc."},{"key":"9322_CR6","volume-title":"STOC","author":"E.W. Chambers","year":"2009","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Homology flows, cohomology cuts. In: STOC (2009)"},{"key":"9322_CR7","volume-title":"Symposium on Computational Geometry","author":"E.W. Chambers","year":"2009","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: Symposium on Computational Geometry (2009)"},{"key":"9322_CR8","unstructured":"Chen, C., Freedman, D.: Quantifying homology classes II: Localization and stability. CoRR, abs\/0709.2512 (2007)"},{"key":"9322_CR9","first-page":"169","volume-title":"Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science","author":"C. Chen","year":"2008","unstructured":"Chen, C., Freedman, D.: Quantifying homology classes. In: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, pp.\u00a0169\u2013180 (2008)"},{"issue":"2","key":"9322_CR10","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.comgeo.2009.06.004","volume":"43","author":"C. Chen","year":"2010","unstructured":"Chen, C., Freedman, D.: Measuring and computing natural generators for homology groups. Comput. Geom. 43(2), 169\u2013181 (2010)","journal-title":"Comput. Geom."},{"key":"9322_CR11","first-page":"119","volume-title":"Proceedings of the 22nd ACM Symposium on Computational Geometry","author":"D. Cohen-Steiner","year":"2006","unstructured":"Cohen-Steiner, D., Edelsbrunner, H., Morozov, D.: Vines and vineyards by updating persistence in linear time. In: Proceedings of the 22nd ACM Symposium on Computational Geometry, pp. 119\u2013126 (2006)"},{"key":"9322_CR12","doi-asserted-by":"crossref","first-page":"339","DOI":"10.2140\/agt.2007.7.339","volume":"7","author":"V. Silva de","year":"2007","unstructured":"de Silva, V., Ghrist, R.: Coverage in sensor networks via persistent homology. Algebr. Geom. Topol. 7, 339\u2013358 (2007)","journal-title":"Algebr. Geom. Topol."},{"key":"9322_CR13","first-page":"221","volume-title":"STOC","author":"T.K. Dey","year":"2010","unstructured":"Dey, T.K., Hirani, A.N., Krishnamoorthy, B.: Optimal homologous cycles, total unimodularity, and linear programming. In: STOC, pp. 221\u2013230 (2010)"},{"key":"9322_CR14","volume-title":"IEEE Proc. NASAGEM","author":"T.K. Dey","year":"2007","unstructured":"Dey, T.K., Li, K., Sun, J.: On computing handle and tunnel loops. In: IEEE Proc. NASAGEM (2007)"},{"key":"9322_CR15","doi-asserted-by":"crossref","unstructured":"Dey, T.K., Li, K., Sun, J., Cohen-Steiner, D.: Computing geometry-aware handle and tunnel loops in 3D models. ACM Trans. Graph. 27(3) (2008)","DOI":"10.1145\/1360612.1360644"},{"key":"9322_CR16","first-page":"166","volume-title":"Symposium on Computational Geometry","author":"T.K. Dey","year":"2010","unstructured":"Dey, T.K., Sun, J., Wang, Y.: Approximating loops in a shortest homology basis from point data. In: Symposium on Computational Geometry, pp. 166\u2013175 (2010)"},{"issue":"1","key":"9322_CR17","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00454-003-2948-z","volume":"31","author":"J. Erickson","year":"2004","unstructured":"Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37\u201359 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9322_CR18","volume-title":"SODA","author":"J. Erickson","year":"2011","unstructured":"Erickson, J., Nayyeri, A.: Minimum cuts and shortest non-separating cycles via homology covers. In: SODA (2011)"},{"key":"9322_CR19","first-page":"1038","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"J. Erickson","year":"2005","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1038\u20131046 (2005)"},{"key":"9322_CR20","first-page":"187","volume-title":"Mobile Networks and Applications","author":"Q. Fang","year":"2006","unstructured":"Fang, Q., Gao, J., Guibas, L.: Locating and bypassing routing holes in sensor networks. In: Mobile Networks and Applications, vol.\u00a011, pp. 187\u2013200 (2006)"},{"key":"9322_CR21","first-page":"19","volume-title":"Proceedings of the Graphics Interface 2004 Conference","author":"I. Guskov","year":"2001","unstructured":"Guskov, I., Wood, Z.J.: Topological noise removal. In: Proceedings of the Graphics Interface 2004 Conference, pp. 19\u201326 (2001)"},{"key":"9322_CR22","unstructured":"Kirsanov, D., Gortler, S.J.: A discrete global minimization algorithm for continuous variational problems. Technical Report TR-14-04, Harvard University (2004)"},{"key":"9322_CR23","volume-title":"Information Theory, Inference & Learning Algorithms","author":"D.J.C. MacKay","year":"2002","unstructured":"MacKay, D.J.C.: Information Theory, Inference & Learning Algorithms. Cambridge University Press, Cambridge (2002)"},{"key":"9322_CR24","volume-title":"Elements of Algebraic Topology","author":"J.R. Munkres","year":"1984","unstructured":"Munkres, J.R.: Elements of Algebraic Topology. Addison\u2013Wesley, Redwood (1984)"},{"issue":"1","key":"9322_CR25","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/s00454-008-9053-2","volume":"39","author":"P. Niyogi","year":"2008","unstructured":"Niyogi, P., Smale, S., Weinberger, S.: Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom. 39(1), 419\u2013441 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"9322_CR26","first-page":"121","volume-title":"Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN\u201909)","author":"R. Sarkar","year":"2009","unstructured":"Sarkar, R., Yin, X., Gao, J., Luo, F., Gu, X.D.: Greedy routing with guaranteed delivery using Ricci flows. In: Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN\u201909), pp. 121\u2013132 (2009)"},{"key":"9322_CR27","unstructured":"Wikipedia. Book embedding. http:\/\/en.wikipedia.org\/wiki\/Book_embedding"},{"key":"9322_CR28","unstructured":"Wikipedia. Suspension. http:\/\/en.wikipedia.org\/wiki\/Suspension_(topology)"},{"issue":"2","key":"9322_CR29","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1145\/990002.990007","volume":"23","author":"Z.J. Wood","year":"2004","unstructured":"Wood, Z.J., Hoppe, H., Desbrun, M., Schr\u00f6der, P.: Removing excess topology from isosurfaces. ACM Trans. Graph. 23(2), 190\u2013208 (2004)","journal-title":"ACM Trans. Graph."},{"key":"9322_CR30","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1109\/SMI.2007.25","volume-title":"Proceedings of the 2007 International Conference on Shape Modeling and Applications","author":"A. Zomorodian","year":"2007","unstructured":"Zomorodian, A., Carlsson, G.: Localized homology. In: Proceedings of the 2007 International Conference on Shape Modeling and Applications, pp. 189\u2013198 (2007)"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9322-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-010-9322-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-010-9322-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T20:40:14Z","timestamp":1559940014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-010-9322-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,14]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9322"],"URL":"https:\/\/doi.org\/10.1007\/s00454-010-9322-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,14]]}}}