{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T11:54:25Z","timestamp":1781524465724,"version":"3.54.1"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> Monophonic, geodesic and 2-geodesic convexities ([Formula: see text]-convexity, [Formula: see text]-convexity and [Formula: see text]-convexity, for short) on graphs are based on the families of induced paths, shortest paths and shortest paths of length [Formula: see text], respectively. We introduce a class of graphs, the class of cross-cyclicgraphs, in which every connected [Formula: see text]-convex set is also [Formula: see text]-convex and [Formula: see text]-convex. We show that this class is properly contained in the class, say [Formula: see text], of graphs in which geodesic and monophonic convexities are equivalent and properly contains the class of distance-hereditary graphs. Moreover, we show that (1) an [Formula: see text]-hull set (i.e., a subset of vertices, with minimum cardinality, whose [Formula: see text]-convex hull equals the whole vertex set) and, hence, the m-hull number and the g-hull number of a graph in [Formula: see text] can be computed in polynomial time and that (2) both the geodesic-convex hull and the monophonic-convex hull can be computed in linear time in a cross-cyclic graph without cycles of length [Formula: see text] and, hence, in a bipartite distance-hereditary graph. <\/jats:p>","DOI":"10.1142\/s1793830918500428","type":"journal-article","created":{"date-parts":[[2018,3,28]],"date-time":"2018-03-28T06:56:06Z","timestamp":1522220166000},"page":"1850042","source":"Crossref","is-referenced-by-count":1,"title":["Two classes of graphs in which some problems related to convexity are efficiently solvable"],"prefix":"10.1142","volume":"10","author":[{"given":"Marina","family":"Moscarini","sequence":"first","affiliation":[{"name":"Department of Computer Science, Sapienza University of Rome, Via Salaria 113, 00198 Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco M.","family":"Malvestuto","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Sapienza University of Rome, Via Salaria 113, 00198 Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2018,6,3]]},"reference":[{"key":"S1793830918500428BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2013.10.017"},{"key":"S1793830918500428BIB002","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013715518448"},{"key":"S1793830918500428BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.04.020"},{"key":"S1793830918500428BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.11.016"},{"key":"S1793830918500428BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90039-1"},{"key":"S1793830918500428BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/0607049"},{"key":"S1793830918500428BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/15M1013389"},{"key":"S1793830918500428BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90510-Z"},{"key":"S1793830918500428BIB009","doi-asserted-by":"publisher","DOI":"10.5402\/2011\/806193"},{"issue":"4","key":"S1793830918500428BIB010","first-page":"1","volume":"4","author":"Malvestuto F. M.","year":"2012","journal-title":"Discrete Math. Alg. Appl."},{"key":"S1793830918500428BIB011","first-page":"1065","volume":"15","author":"Sampathkumar E.","year":"1984","journal-title":"Indian J. Pure Appl. Math."},{"issue":"4","key":"S1793830918500428BIB012","first-page":"3","volume":"36","author":"Soltan V. P.","year":"1991","journal-title":"Studia Univ. Babes-Bolyai Math."},{"key":"S1793830918500428BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90051-2"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830918500428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:00:15Z","timestamp":1565114415000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830918500428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":13,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2018,6,3]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S1793830918500428"],"URL":"https:\/\/doi.org\/10.1142\/s1793830918500428","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}