{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T07:10:29Z","timestamp":1686294629058},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,9,3]],"date-time":"2011-09-03T00:00:00Z","timestamp":1315008000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s00453-011-9561-y","type":"journal-article","created":{"date-parts":[[2011,9,6]],"date-time":"2011-09-06T16:58:25Z","timestamp":1315328305000},"page":"645-671","source":"Crossref","is-referenced-by-count":1,"title":["Counting Hexagonal Patches and Independent Sets in Circle Graphs"],"prefix":"10.1007","volume":"63","author":[{"given":"Paul","family":"Bonsma","sequence":"first","affiliation":[]},{"given":"Felix","family":"Breuer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,3]]},"reference":[{"key":"9561_CR1","unstructured":"Blank, S.J.: Extending immersions of the circle. Ph.D. thesis, Brandeis University, Waltham, MA, USA (1967)"},{"key":"9561_CR2","unstructured":"Bonsma, P., Breuer, F.: Finding fullerene patches in polynomial time I: counting hexagonal patches. arXiv: 0808.3881v1 (2008)"},{"key":"9561_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1007\/978-3-642-10631-6_76","volume-title":"Proceedings of the 20th International Symposium on Algorithm and Computation (ISAAC 2009)","author":"P. Bonsma","year":"2009","unstructured":"Bonsma, P., Breuer, F.: Finding fullerene patches in polynomial time. In: Proceedings of the 20th International Symposium on Algorithm and Computation (ISAAC 2009). Lecture Notes in Computer Science, vol. 5878, pp. 750\u2013759. Springer, Berlin (2009)"},{"issue":"5","key":"9561_CR4","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1016\/S0195-6698(03)00034-9","volume":"24","author":"J. Bornh\u00f6ft","year":"2003","unstructured":"Bornh\u00f6ft, J., Brinkmann, G., Greinus, J.: Pentagon\u2013hexagon-patches with short boundaries. Eur. J. Comb. 24(5), 517\u2013529 (2003)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"9561_CR5","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF02579301","volume":"7","author":"A. Bouchet","year":"1987","unstructured":"Bouchet, A.: Reducing prime graphs and recognizing circle graphs. Combinatorica 7(3), 243\u2013254 (1987)","journal-title":"Combinatorica"},{"key":"9561_CR6","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"issue":"1","key":"9561_CR7","first-page":"209","volume":"62","author":"G. Brinkmann","year":"2009","unstructured":"Brinkmann, G., Coppens, B.: An efficient algorithm for the generation of planar polycyclic hydrocarbons with a given boundary. MATCH Commun. Math. Comput. Chem. 62(1), 209\u2013220 (2009)","journal-title":"MATCH Commun. Math. Comput. Chem."},{"issue":"2","key":"9561_CR8","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1006\/jagm.1996.0806","volume":"23","author":"G. Brinkmann","year":"1997","unstructured":"Brinkmann, G., Dress, A.W.M.: A constructive enumeration of fullerenes. J. Algorithms 23(2), 345\u2013358 (1997)","journal-title":"J. Algorithms"},{"issue":"1\u20132","key":"9561_CR9","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0166-218X(00)00328-0","volume":"116","author":"G. Brinkmann","year":"2002","unstructured":"Brinkmann, G., Nathusius, U. v., Palser, A.H.R.: A constructive enumeration of nanotube caps. Discrete Appl. Math. 116(1\u20132), 55\u201371 (2002)","journal-title":"Discrete Appl. Math."},{"key":"9561_CR10","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"27","volume-title":"Graphs and Discovery, Proceedings of the DIMACS Workshop on Computer Generated Conjectures from Graph Theoretic and Chemical Databases","author":"G. Brinkmann","year":"2005","unstructured":"Brinkmann, G., Delgado-Friedrichs, O., von Nathusius, U.: Numbers of faces and boundary encodings of patches. In: Graphs and Discovery, Proceedings of the DIMACS Workshop on Computer Generated Conjectures from Graph Theoretic and Chemical Databases. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 69, pp. 27\u201338. AMS, Providence (2005)"},{"issue":"2","key":"9561_CR11","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s10910-008-9403-6","volume":"45","author":"G. Brinkmann","year":"2009","unstructured":"Brinkmann, G., Graver, J.E., Justus, C.: Numbers of faces in disordered patches. J. Math. Chem. 45(2), 263\u2013278 (2009)","journal-title":"J. Math. Chem."},{"key":"9561_CR12","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1021\/ci000060o","volume":"41","author":"M. Deza","year":"2001","unstructured":"Deza, M., Fowler, P.W., Grishukhin, V.: Allowed boundary sequences for fused polycyclic patches and related algorithmic problems. J. Chem. Inf. Comput. Sci. 41, 300\u2013308 (2001)","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"9561_CR13","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005)","edition":"3"},{"issue":"9","key":"9561_CR14","doi-asserted-by":"crossref","first-page":"1518","DOI":"10.1016\/j.dam.2006.11.020","volume":"156","author":"M. Dutour Sikiri\u0107","year":"2008","unstructured":"Dutour Sikiri\u0107, M., Deza, M., Shtogrin, M.: Filling of a given boundary by p-gons and related problems. Discrete Appl. Math. 156(9), 1518\u20131535 (2008)","journal-title":"Discrete Appl. Math."},{"key":"9561_CR15","doi-asserted-by":"crossref","first-page":"6941","DOI":"10.1021\/j100196a017","volume":"96","author":"M. Endo","year":"1992","unstructured":"Endo, M., Kroto, H.W.: Formation of carbon nanofibers. J. Phys. Chem. 96, 6941\u20136944 (1992)","journal-title":"J. Phys. Chem."},{"key":"9561_CR16","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1137\/1.9781611973068.19","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D. Eppstein","year":"2009","unstructured":"Eppstein, D., Mumford, E.: Self-overlapping curves revisited. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 160\u2013169. SIAM, Philadelphia (2009)"},{"issue":"4","key":"9561_CR17","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1307\/mmj\/1029000526","volume":"17","author":"G.K. Francis","year":"1970","unstructured":"Francis, G.K.: Extensions to the disk of properly nested plane immersions of the circle. Mich. Math. J. 17(4), 377\u2013383 (1970)","journal-title":"Mich. Math. J."},{"issue":"3","key":"9561_CR18","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/65950.65951","volume":"36","author":"C.P. Gabor","year":"1989","unstructured":"Gabor, C.P., Supowit, K.J., Hsu, W.L.: Recognizing circle graphs in polynomial time. J. ACM 36(3), 435\u2013473 (1989)","journal-title":"J. ACM"},{"issue":"3","key":"9561_CR19","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F. Gavril","year":"1973","unstructured":"Gavril, F.: Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks 3(3), 261\u2013273 (1973)","journal-title":"Networks"},{"key":"9561_CR20","first-page":"189","volume":"48","author":"J.E. Graver","year":"2003","unstructured":"Graver, J.E.: The (m,k)-patch boundary code problem. MATCH Commun. Math. Comput. Chem. 48, 189\u2013196 (2003)","journal-title":"MATCH Commun. Math. Comput. Chem."},{"issue":"3","key":"9561_CR21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0166-218X(01)00180-9","volume":"118","author":"X. Guo","year":"2002","unstructured":"Guo, X., Hansen, P., Zheng, M.: Boundary uniqueness of fusenes. Discrete Appl. Math. 118(3), 209\u2013222 (2002)","journal-title":"Discrete Appl. Math."},{"key":"9561_CR22","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. John Hopkins University Press, Baltimore (2001)"},{"key":"9561_CR23","volume":"13","author":"N. Nash","year":"2008","unstructured":"Nash, N., Lelait, S., Gregg, D.: Efficiently implementing maximum independent set algorithms on circle graphs. ACM J. Exp. Algorithmics 13, 1.9 (2008)","journal-title":"ACM J. Exp. Algorithmics"},{"issue":"1","key":"9561_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009330","volume":"19","author":"R. Seidel","year":"1998","unstructured":"Seidel, R.: The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom. 19(1), 1\u201317 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9561_CR25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0925-7721(92)90019-O","volume":"2","author":"P.W. Shor","year":"1992","unstructured":"Shor, P.W., Van Wyk, C.J.: Detecting and decomposing self-overlapping curves. Comput. Geom. 2(1), 31\u201350 (1992)","journal-title":"Comput. Geom."},{"issue":"2","key":"9561_CR26","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1006\/jagm.1994.1012","volume":"16","author":"J.P. Spinrad","year":"1994","unstructured":"Spinrad, J.P.: Recognition of circle graphs. J. Algorithms 16(2), 264\u2013282 (1994)","journal-title":"J. Algorithms"},{"issue":"1","key":"9561_CR27","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TCAD.1987.1270250","volume":"6","author":"K.J. Supowit","year":"1987","unstructured":"Supowit, K.J.: Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 6(1), 93\u201394 (1987)","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"9561_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-3-540-24587-2_15","volume-title":"Proceedings of the 14th International Symposium on Algorithm and Computation (ISAAC 2003)","author":"G. Valiente","year":"2003","unstructured":"Valiente, G.: A new simple algorithm for the maximum-weight independent set problem on circle graphs. In: Proceedings of the 14th International Symposium on Algorithm and Computation (ISAAC 2003). Lecture Notes in Computer Science, vol. 2906, pp. 129\u2013137. Springer, Berlin (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9561-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9561-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9561-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T06:41:04Z","timestamp":1686292864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9561-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,3]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["9561"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9561-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,3]]}}}