{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:46:53Z","timestamp":1770972413338,"version":"3.50.1"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030392185","type":"print"},{"value":"9783030392192","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-39219-2_9","type":"book-chapter","created":{"date-parts":[[2020,1,24]],"date-time":"2020-01-24T19:09:24Z","timestamp":1579892964000},"page":"102-115","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Hardness and Approximation for the Geodetic Set Problem in Some Graph Classes"],"prefix":"10.1007","author":[{"given":"Dibyayan","family":"Chakraborty","sequence":"first","affiliation":[]},{"given":"Florent","family":"Foucaud","sequence":"additional","affiliation":[]},{"given":"Harmender","family":"Gahlawat","sequence":"additional","affiliation":[]},{"given":"Subir Kumar","family":"Ghosh","sequence":"additional","affiliation":[]},{"given":"Bodhayan","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,1,24]]},"reference":[{"issue":"5","key":"9_CR1","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1080\/00207160210954","volume":"79","author":"M Atici","year":"2002","unstructured":"Atici, M.: Computational complexity of geodetic set. Int. J. Comput. Math. 79(5), 587\u2013591 (2002)","journal-title":"Int. J. Comput. Math."},{"issue":"4","key":"9_CR2","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1080\/16073606.1985.9631921","volume":"8","author":"F Buckley","year":"1985","unstructured":"Buckley, F., Harary, F.: Geodetic games for graphs. Quaestiones Math. 8(4), 321\u2013334 (1985)","journal-title":"Quaestiones Math."},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.ipl.2018.02.012","volume":"135","author":"LR Bueno","year":"2018","unstructured":"Bueno, L.R., Penso, L.D., Protti, F., Ramos, V.R., Rautenbach, D., Souza, U.S.: On the hardness of finding the geodetic number of a subcubic graph. Inf. Process. Lett. 135, 22\u201327 (2018)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1137\/060652063","volume":"22","author":"G C\u0103linescu","year":"2008","unstructured":"C\u0103linescu, G., Dumitrescu, A., Pach, J.: Reconfigurations in graphs and grids. SIAM J. Discrete Math. 22(1), 124\u2013138 (2008)","journal-title":"SIAM J. Discrete Math."},{"issue":"11","key":"9_CR5","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206(11), 1264\u20131275 (2008)","journal-title":"Inf. Comput."},{"key":"9_CR6","unstructured":"Chuzhoy, J., Kim, D.H.K.: On approximating node-disjoint paths in grids. In: APPROX\/RANDOM, pp. 187\u2013211. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: STOC, pp. 624\u2013633. ACM (2014)","DOI":"10.1145\/2591796.2591884"},{"issue":"4","key":"9_CR8","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1016\/j.disc.2009.09.018","volume":"310","author":"MC Dourado","year":"2010","unstructured":"Dourado, M.C., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Some remarks on the geodetic number of a graph. Discrete Math. 310(4), 832\u2013837 (2010)","journal-title":"Discrete Math."},{"key":"9_CR9","unstructured":"Dourado, M.C., Protti, F., Szwarcfiter, J.L.: On the complexity of the geodetic and convexity numbers of a graph. In: ICDM, vol. 7, pp. 101\u2013108. Ramanujan Mathematical Society (2008)"},{"issue":"4","key":"9_CR10","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1051\/ro\/2014019","volume":"48","author":"T Ekim","year":"2014","unstructured":"Ekim, T., Erey, A.: Block decomposition approach to compute a minimum geodetic set. RAIRO-Oper. Res. 48(4), 497\u2013507 (2014)","journal-title":"RAIRO-Oper. Res."},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-29344-3_24","volume-title":"LATIN 2012: Theoretical Informatics","author":"T Ekim","year":"2012","unstructured":"Ekim, T., Erey, A., Heggernes, P., van\u2019t Hof, P., Meister, D.: Computing minimum geodetic sets of proper interval graphs. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 279\u2013290. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-29344-3_24"},{"issue":"3","key":"9_CR12","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/0607049","volume":"7","author":"M Farber","year":"1986","unstructured":"Farber, M., Jamison, R.E.: Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Methods 7(3), 433\u2013444 (1986)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"9_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H.Freeman, New York (2002)"},{"issue":"3","key":"9_CR14","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s00373-002-0517-5","volume":"19","author":"MU Gerber","year":"2003","unstructured":"Gerber, M.U., Lozin, V.V.: Robust algorithms for the stable set problem. Graphs Comb. 19(3), 347\u2013356 (2003)","journal-title":"Graphs Comb."},{"issue":"1","key":"9_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230240104","volume":"24","author":"O Gerstel","year":"1994","unstructured":"Gerstel, O., Zaks, S.: A new characterization of tree medians with applications to distributed sorting. Networks 24(1), 23\u201329 (1994)","journal-title":"Networks"},{"issue":"4","key":"9_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0020-0190(89)90118-X","volume":"31","author":"A Gregori","year":"1989","unstructured":"Gregori, A.: Unit-length embedding of binary trees on a square grid. Inf. Process. Lett. 31(4), 167\u2013173 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"2\u20133","key":"9_CR17","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0166-218X(99)00056-6","volume":"92","author":"V Guruswami","year":"1999","unstructured":"Guruswami, V.: Maximum cut on line and total graphs. Discrete Appl. Math. 92(2\u20133), 217\u2013221 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"11","key":"9_CR18","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0895-7177(93)90259-2","volume":"17","author":"F Harary","year":"1993","unstructured":"Harary, F., Loukakis, E., Tsouros, C.: The geodetic number of a graph. Math. Comput. Modell. 17(11), 89\u201395 (1993)","journal-title":"Math. Comput. Modell."},{"issue":"4","key":"9_CR19","doi-asserted-by":"publisher","first-page":"389","DOI":"10.2989\/16073600309486069","volume":"26","author":"TW Haynes","year":"2003","unstructured":"Haynes, T.W., Henning, M., Tiller, C.A.: Geodetic achievement and avoidance games for graphs. Quaestiones Math. 26(4), 389\u2013397 (2003)","journal-title":"Quaestiones Math."},{"issue":"4","key":"9_CR20","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676\u2013686 (1982)","journal-title":"SIAM J. Comput."},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2018.05.032","volume":"745","author":"M Mezzini","year":"2018","unstructured":"Mezzini, M.: Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs. Theoret. Comput. Sci. 745, 63\u201374 (2018)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0012-365X(78)90098-5","volume":"24","author":"SL Mitchell","year":"1978","unstructured":"Mitchell, S.L.: Another characterization of the centroid of a tree. Discrete Math. 24(3), 277\u2013280 (1978)","journal-title":"Discrete Math."},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.dam.2015.10.022","volume":"204","author":"AA Sardroud","year":"2016","unstructured":"Sardroud, A.A., Bagheri, A.: An approximation algorithm for the longest cycle problem in solid grid graphs. Discrete Appl. Math. 204, 6\u201312 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9_CR24","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1007\/s00453-017-0278-4","volume":"79","author":"S Tirodkar","year":"2017","unstructured":"Tirodkar, S., Vishwanathan, S.: On the approximability of the minimum rainbow subgraph problem and other related problems. Algorithmica 79(3), 909\u2013924 (2017)","journal-title":"Algorithmica"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-642-24983-9_19","volume-title":"Computational Geometry, Graphs and Applications","author":"BY Wu","year":"2011","unstructured":"Wu, B.Y.: A 7\/6-approximation algorithm for the max-min connected bipartition problem on grid graphs. In: Akiyama, J., Bo, J., Kano, M., Tan, X. (eds.) CGGA 2010. LNCS, vol. 7033, pp. 188\u2013194. Springer, Heidelberg (2011). \nhttps:\/\/doi.org\/10.1007\/978-3-642-24983-9_19"},{"issue":"3","key":"9_CR26","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. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"issue":"39","key":"9_CR27","doi-asserted-by":"publisher","first-page":"5340","DOI":"10.1016\/j.tcs.2011.06.010","volume":"412","author":"W Zhang","year":"2011","unstructured":"Zhang, W., Liu, Y.: Approximating the longest paths in grid graphs. Theoret. Comput. Sci. 412(39), 5340\u20135350 (2011)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-39219-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,25]],"date-time":"2020-01-25T00:01:45Z","timestamp":1579910505000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-39219-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030392185","9783030392192"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-39219-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"24 January 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hyderabad","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 February 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iith.ac.in\/~caldam2020\/index.php","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}