{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T22:13:27Z","timestamp":1743113607438,"version":"3.40.3"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030271947"},{"type":"electronic","value":"9783030271954"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-27195-4_25","type":"book-chapter","created":{"date-parts":[[2019,8,1]],"date-time":"2019-08-01T09:03:14Z","timestamp":1564650194000},"page":"272-283","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A General Framework for Path Convexities"],"prefix":"10.1007","author":[{"given":"Jo\u00e3o Vinicius C.","family":"Thompson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Loana T.","family":"Nogueira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F\u00e1bio","family":"Protti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raquel S. F.","family":"Bravo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mitre C.","family":"Dourado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U\u00e9verton S.","family":"Souza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,1]]},"reference":[{"key":"25_CR1","first-page":"109","volume":"44","author":"RT Araujo","year":"2013","unstructured":"Araujo, R.T., Sampaio, R.M., Szwarcfiter, J.L.: The convexity of induced paths of order three. Discrete Math. 44, 109\u2013114 (2013)","journal-title":"Discrete Math."},{"issue":"2","key":"25_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"25_CR3","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, 587\u2013591 (2002)","journal-title":"Int. J. Comput. Math."},{"issue":"1\u20132","key":"25_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, vol. 3. SIAM, Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"issue":"4","key":"25_CR6","doi-asserted-by":"publisher","first-page":"685","DOI":"10.7151\/dmgt.1638","volume":"32","author":"J C\u00e1ceres","year":"2012","unstructured":"C\u00e1ceres, J., Oellermann, O.R., Puertas, M.L.: Minimal trees and monophonic convexity. Discuss. Math. Graph Theory 32(4), 685\u2013704 (2012)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"5","key":"25_CR7","first-page":"175","volume":"12","author":"CC Centeno","year":"2010","unstructured":"Centeno, C.C., Dantas, S., Dourado, M.C., Rautenbach, D., Szwarcfiter, J.L.: Convex partitions of graphs induced by paths of order three. Discrete Math. 12(5), 175\u2013184 (2010)","journal-title":"Discrete Math."},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"3693","DOI":"10.1016\/j.tcs.2011.03.029","volume":"412","author":"CC Centeno","year":"2011","unstructured":"Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible interval of graphs. Theoret. Comput. Sci. 412, 3693\u20133700 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.endm.2009.02.003","volume":"32","author":"CC Centeno","year":"2009","unstructured":"Centeno, C.C., Dourado, M.C., Szwarcfiter, J.L.: On the convexity of paths of length two in undirected graphs. Electron. Notes Discrete Math. 32, 11\u201318 (2009)","journal-title":"Electron. Notes Discrete Math."},{"key":"25_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0012-365X(98)00394-X","volume":"206","author":"M Changat","year":"1999","unstructured":"Changat, M., Mathew, J.: On triangle path convexity in graphs. Discrete Math. 206, 91\u201395 (1999)","journal-title":"Discrete Math."},{"issue":"3","key":"25_CR11","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.disc.2004.02.017","volume":"286","author":"M Changat","year":"2004","unstructured":"Changat, M., Mathew, J.: Induced path transit function, monotone and Peano axioms. Discrete Math. 286(3), 185\u2013194 (2004)","journal-title":"Discrete Math."},{"issue":"2","key":"25_CR12","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1023\/A:1013715518448","volume":"51","author":"M Changat","year":"2001","unstructured":"Changat, M., Klavzar, S., Mulder, H.M.: The all-paths transit function of a graph. Czechoslovak Mathematic J. 51(2), 439\u2013448 (2001)","journal-title":"Czechoslovak Mathematic J."},{"issue":"2\u20133","key":"25_CR13","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.disc.2003.07.014","volume":"290","author":"M Changat","year":"2005","unstructured":"Changat, M., Mulder, H.M., Sierksma, G.: Convexities related to path properties on graphs. Discrete Math. 290(2\u20133), 117\u2013131 (2005)","journal-title":"Discrete Math."},{"issue":"6","key":"25_CR14","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.1016\/j.disc.2008.02.043","volume":"309","author":"M Changat","year":"2009","unstructured":"Changat, M., Narasimha-Shenoi, P.G., Mathews, J.: Triangle path transit functions, betweenness and pseudo-modular graphs. Discrete Math. 309(6), 1575\u20131583 (2009)","journal-title":"Discrete Math."},{"key":"25_CR15","first-page":"111","volume":"82","author":"M Changat","year":"2010","unstructured":"Changat, M., Narasimha-Shenoi, P.G., Pelayo, I.: The longest path transit function of a graph and betweenness. Utilitas Mathematica 82, 111\u2013127 (2010)","journal-title":"Utilitas Mathematica"},{"key":"25_CR16","first-page":"97","volume":"64","author":"G Chartrand","year":"2003","unstructured":"Chartrand, G., Garry, L., Zhang, P.: The detour number of a graph. Utilitas Mathematica 64, 97\u2013113 (2003)","journal-title":"Utilitas Mathematica"},{"key":"25_CR17","first-page":"75","volume":"52","author":"G Chartrand","year":"2005","unstructured":"Chartrand, G., Escuadro, H., Zhang, P.: Detour distance in graphs. J. Combin. Math. Combin. Comput. 52, 75\u201394 (2005)","journal-title":"J. Combin. Math. Combin. Comput."},{"issue":"2","key":"25_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0166-218X(96)00007-8","volume":"73","author":"V Chepoi","year":"1997","unstructured":"Chepoi, V.: Peakless functions on graphs. Discrete Appl. Math. 73(2), 175\u2013189 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"25_CR19","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"Bruno Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 25(1), 12\u201375 (1990)","journal-title":"Information and Computation"},{"issue":"3","key":"25_CR20","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita\/1992260302571","volume":"26","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues. Informatique Th\u00e9orique et Appl. 26, 257\u2013286 (1992)","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"issue":"1","key":"25_CR21","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theoret. Comput. Sci. 109(1), 49\u201382 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR22","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1142\/9789812384720_0005","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformation","author":"B. COURCELLE","year":"1997","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of Graph Grammars and Computing by Graph Transformations, vol. 1, pp. 313\u2013400 (1997)"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Cambridge University Press, Cambridge (2011)","DOI":"10.1017\/CBO9780511977619"},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-14279-6_7","volume-title":"Graph Theory","author":"Reinhard Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)"},{"key":"25_CR25","doi-asserted-by":"publisher","first-page":"5668","DOI":"10.1016\/j.disc.2008.04.020","volume":"309","author":"MC Dourado","year":"2009","unstructured":"Dourado, M.C., Gimbel, J.G., Kratochvil, J., Protti, F., Szwarcfiter, J.L.: On the computation of the hull number of a graph. Discrete Math. 309, 5668\u20135674 (2009)","journal-title":"Discrete Math."},{"key":"25_CR26","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1016\/j.dam.2009.11.016","volume":"158","author":"MC Dourado","year":"2010","unstructured":"Dourado, M.C., Protti, F., Szwarcfiter, J.L.: Complexity results related to monophonic convexity. Discrete Math. 158, 1268\u20131274 (2010)","journal-title":"Discrete Math."},{"issue":"16","key":"25_CR27","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1016\/j.disc.2012.05.002","volume":"312","author":"MC Dourado","year":"2012","unstructured":"Dourado, M.C., Rautenbach, D., dos Santos, V.F., Sch\u00e4fer, P.M., Szwarcfiter, J.L., Toman, A.: An upper bound on the $$P_3$$-radon number. Discrete Math. 312(16), 2433\u20132437 (2012)","journal-title":"Discrete Math."},{"key":"25_CR28","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.dam.2016.01.015","volume":"206","author":"MC Dourado","year":"2016","unstructured":"Dourado, M.C., Sampaio, R.M.: Complexity aspects of the triangle path convexity. Discrete Appl. Math. 206, 39\u201347 (2016)","journal-title":"Discrete Appl. Math."},{"key":"25_CR29","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/S0895480195321718","volume":"12","author":"FF Dragan","year":"1999","unstructured":"Dragan, F.F., Nicolai, F., Brandst\u00e4dt, A.: Convexity and HHD-free graphs. SIAM J. Discrete Math. 12, 119\u2013135 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"25_CR30","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0095-8956(88)90039-1","volume":"44","author":"Pierre Duchet","year":"1988","unstructured":"Duchet, P.: Convex sets in graphs, II. Minimal path convexity. J. Comb. Theory Ser. B 44, 307\u2013316 (1988)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"25_CR31","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. Alg. Disc. Math. 7(3), 433\u2013444 (1986)","journal-title":"SIAM J. Alg. Disc. Math."},{"key":"25_CR32","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0012-365X(87)90099-9","volume":"66","author":"M Farber","year":"1987","unstructured":"Farber, M., Jamison, R.E.: On local convexity in graphs. Discrete Math. 66, 231\u2013247 (1987)","journal-title":"Discrete Math."},{"key":"25_CR33","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00373-002-0518-4","volume":"19","author":"JG Gimbel","year":"2003","unstructured":"Gimbel, J.G.: Some remarks on the convexity number of a graph. Graphs Comb. 19, 357\u2013361 (2003)","journal-title":"Graphs Comb."},{"issue":"7","key":"25_CR34","doi-asserted-by":"publisher","first-page":"1660","DOI":"10.1016\/j.dam.2008.07.010","volume":"157","author":"G Gutin","year":"2009","unstructured":"Gutin, G., Yeo, A.: On the number of connected convex subgraphs of a connected acyclic digraph. Discrete Appl. Math. 157(7), 1660\u20131662 (2009)","journal-title":"Discrete Appl. Math."},{"key":"25_CR35","first-page":"323","volume":"20","author":"F Harary","year":"1984","unstructured":"Harary, F.: Convexity in graphs: achievement and avoidance games. Ann. Discrete Math. 20, 323 (1984)","journal-title":"Ann. Discrete Math."},{"key":"25_CR36","doi-asserted-by":"publisher","first-page":"185","DOI":"10.4310\/jdg\/1214436096","volume":"16","author":"F Harary","year":"1981","unstructured":"Harary, F., Nieminen, J.: Convexity in graphs. J. Differ. Geom. 16, 185\u2013190 (1981)","journal-title":"J. Differ. Geom."},{"issue":"11","key":"25_CR37","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. Model. 17(11), 89\u201395 (1993)","journal-title":"Math. Comput. Model."},{"key":"25_CR38","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.tcs.2005.10.021","volume":"351","author":"R Haas","year":"2006","unstructured":"Haas, R., Hoffmann, M.: Chordless path through three vertices. Theoret. Comput. Sci. 351, 360\u2013371 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/978-3-642-35843-2_24","volume-title":"SOFSEM 2013: Theory and Practice of Computer Science","author":"MM Kant\u00e9","year":"2013","unstructured":"Kant\u00e9, M.M., Nourine, L.: Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 268\u2013279. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-35843-2_24"},{"issue":"1","key":"25_CR40","doi-asserted-by":"crossref","first-page":"173","DOI":"10.21136\/CMJ.1994.128449","volume":"44","author":"L Nebesk\u00fd","year":"1994","unstructured":"Nebesk\u00fd, L.: A characterization of the interval function of a connected graph. Czechoslovak Math. J. 44(1), 173\u2013178 (1994)","journal-title":"Czechoslovak Math. J."},{"issue":"2","key":"25_CR41","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1137\/070691383","volume":"23","author":"MH Nielsen","year":"2011","unstructured":"Nielsen, M.H., Oellermann, O.R.: Steiner trees and convex geometries. SIAM J. Discrete Math. 23(2), 680\u2013693 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"25_CR42","first-page":"177","volume":"36","author":"DB Parker","year":"2006","unstructured":"Parker, D.B., Westhoff, R.F., Wolf, M.J.: Two-path convexity in clone-free regular multipartite tournaments. Australas. J. Combin. 36, 177\u2013196 (2006)","journal-title":"Australas. J. Combin."},{"key":"25_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-8699-2","volume-title":"Geodesic Convexity in Graphs","author":"IM Pelayo","year":"2013","unstructured":"Pelayo, I.M.: Geodesic Convexity in Graphs. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-8699-2"},{"key":"25_CR44","unstructured":"Parvathy, K.S.: Studies on convex structures with emphasis on convexity in graphs. Ph.D. thesis, Cochin University, Kochi (1995)"},{"key":"25_CR45","first-page":"2153","volume":"312","author":"I Peterin","year":"2012","unstructured":"Peterin, I.: The pre-hull number and lexicographic product. Discrete Appl. Math. 312, 2153\u20132157 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"10","key":"25_CR46","first-page":"1065","volume":"15","author":"E Sampathkumar","year":"1984","unstructured":"Sampathkumar, E.: Convex sets in a graph. Indian J. Pure Appl. Math. 15(10), 1065\u20131071 (1984)","journal-title":"Indian J. Pure Appl. Math."},{"issue":"2","key":"25_CR47","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup, M.: All structured programs have small tree width and good register allocation. Inf. Comput. 142(2), 159\u2013181 (1998)","journal-title":"Inf. Comput."},{"key":"25_CR48","unstructured":"van de Vel, M.L.J.: Theory of Convex Structures. North Holland, Amsterdam (1993)"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-27195-4_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:18:12Z","timestamp":1709824692000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-27195-4_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030271947","9783030271954"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-27195-4_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"1 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Applications in Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/theory.ict.ac.cn\/aaim2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}