{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:52:12Z","timestamp":1753887132142,"version":"3.41.2"},"reference-count":19,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,12,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This article formalizes an algorithm that computes the minimum toll sets in an undirected graph. A core process in our algorithm is to check vertex subsets in order of size. We add a new flavor to the implementation of this process; when the <jats:inline-formula>\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_comp-2023-0103_eq_001.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mi>k<\/m:mi>\n                           <m:mo>\u2212<\/m:mo>\n                           <m:mn>1<\/m:mn>\n                        <\/m:math>\n                        <jats:tex-math>k-1<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>-vertex subsets are already constructed, our algorithm produces the <jats:inline-formula>\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_comp-2023-0103_eq_002.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mi>k<\/m:mi>\n                        <\/m:math>\n                        <jats:tex-math>k<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>-vertex subsets building on the <jats:inline-formula>\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_comp-2023-0103_eq_003.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mi>k<\/m:mi>\n                           <m:mo>\u2212<\/m:mo>\n                           <m:mn>1<\/m:mn>\n                        <\/m:math>\n                        <jats:tex-math>k-1<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>-vertex subsets rather than reconstructing the <jats:inline-formula>\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_comp-2023-0103_eq_004.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mi>k<\/m:mi>\n                        <\/m:math>\n                        <jats:tex-math>k<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>-vertex subsets from the ground up as the existing algorithms would do. Our implementation is usable in combinatorial minimization problems that require checking variable-size combinations in order of size.<\/jats:p>","DOI":"10.1515\/comp-2023-0103","type":"journal-article","created":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T21:28:01Z","timestamp":1703107681000},"source":"Crossref","is-referenced-by-count":0,"title":["A combinatorial algorithm and its application in computing all minimum toll sets of graphs"],"prefix":"10.1515","volume":"13","author":[{"given":"Samer","family":"Nofal","sequence":"first","affiliation":[{"name":"Department of Computer Science, German Jordanian University , Amman , Jordan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2023,12,20]]},"reference":[{"key":"2024050617111940920_j_comp-2023-0103_ref_001","doi-asserted-by":"crossref","unstructured":"L. Alc\u00f3n, B. Bre\u0161ar, T. Gologranc, M. Gutierrez, T. K. \u0160umenjak, I. Peterin, and A. Tepeh, \u201cToll convexity,\u201d European Journal of Combinatorics, vol. 46, pp. 161\u2013175, 2015.","DOI":"10.1016\/j.ejc.2015.01.002"},{"key":"2024050617111940920_j_comp-2023-0103_ref_002","doi-asserted-by":"crossref","unstructured":"M. C. Dourado, \u201cComputing the hull number in toll convexity,\u201d Annals of Operations Research, vol. 315, no. 1, pp. 121\u2013140, 2022.","DOI":"10.1007\/s10479-022-04694-4"},{"key":"2024050617111940920_j_comp-2023-0103_ref_003","doi-asserted-by":"crossref","unstructured":"T. Gologranc and P. Repolusk, \u201cToll number of the strong product of graphs,\u201d Discrete Mathematics, vol. 342, no. 3, pp. 807\u2013814, 2019.","DOI":"10.1016\/j.disc.2018.11.007"},{"key":"2024050617111940920_j_comp-2023-0103_ref_004","doi-asserted-by":"crossref","unstructured":"T. Gologranc and P. Repolusk, \u201cToll number of the cartesian and the lexicographic product of graphs,\u201d Discrete Mathematics, vol. 340, no. 10, pp. 2488\u20132498, 2017.","DOI":"10.1016\/j.disc.2017.06.007"},{"key":"2024050617111940920_j_comp-2023-0103_ref_005","unstructured":"R. L. Arco and S. R. Canoy Jr, \u201cForcing toll convexity numbers of some products of graphs,\u201d Advances and Applications in Mathematical Sciences, vol. 17, no. 5, pp. 401\u2013416, 2018."},{"key":"2024050617111940920_j_comp-2023-0103_ref_006","doi-asserted-by":"crossref","unstructured":"T. Dravec, \u201cOn the toll number of a graph,\u201d Discrete Applied Mathematics, vol. 321, pp. 250\u2013257, 2022.","DOI":"10.1016\/j.dam.2022.07.006"},{"key":"2024050617111940920_j_comp-2023-0103_ref_007","unstructured":"M. van de Vel, Theory of Convex Structures. North-Holland: Elsevier, 1993."},{"key":"2024050617111940920_j_comp-2023-0103_ref_008","doi-asserted-by":"crossref","unstructured":"M. M. Choban, \u201cAbout convex structures on metric spaces,\u201d Carpathian Journal of Mathematics, vol. 38, no. 2, pp. 391\u2013404, 2022.","DOI":"10.37193\/CJM.2022.02.10"},{"key":"2024050617111940920_j_comp-2023-0103_ref_009","doi-asserted-by":"crossref","unstructured":"U. C. SV, M. C. Dourado, and M. G. Thankachy, \u201cComputational and structural aspects of the geodetic and the hull numbers of shadow graphs,\u201d Discrete Applied Mathematics, vol. 307, pp. 50\u201361, 2022.","DOI":"10.1016\/j.dam.2021.10.005"},{"key":"2024050617111940920_j_comp-2023-0103_ref_010","doi-asserted-by":"crossref","unstructured":"B. Pang, \u201cHull operators and interval operators in (l, m)-fuzzy convex spaces,\u201d Fuzzy Sets and Systems, vol. 405, pp. 106\u2013127, 2021.","DOI":"10.1016\/j.fss.2019.11.010"},{"key":"2024050617111940920_j_comp-2023-0103_ref_011","doi-asserted-by":"crossref","unstructured":"L. M. Del Pezzo, A. Quaas, and J. D. Rossi, \u201cFractional convexity,\u201d Mathematische Annalen, vol. 383, no. 3\u20134, pp. 1687\u20131719, 2022.","DOI":"10.1007\/s00208-021-02254-y"},{"key":"2024050617111940920_j_comp-2023-0103_ref_012","doi-asserted-by":"crossref","unstructured":"D. Anderson, P. Bankston, and A. McCluskey, \u201cConvexity in topological betweenness structures,\u201d Topology and Its Applications, vol. 304, pp. 1077\u201383, 2021.","DOI":"10.1016\/j.topol.2021.107783"},{"key":"2024050617111940920_j_comp-2023-0103_ref_013","doi-asserted-by":"crossref","unstructured":"P. Neethu and U. C. SV, \u201cA note on the convexity number of the complementary prisms of trees,\u201d Discrete Applied Mathematics, vol. 319, pp. 480\u2013486, 2022.","DOI":"10.1016\/j.dam.2021.07.033"},{"key":"2024050617111940920_j_comp-2023-0103_ref_014","doi-asserted-by":"crossref","unstructured":"J. Gimbel, \u201cSome remarks on the convexity number of a graph,\u201d Graphs and Combinatorics, vol. 19, no. 3, pp. 357\u2013361, 2003.","DOI":"10.1007\/s00373-002-0518-4"},{"key":"2024050617111940920_j_comp-2023-0103_ref_015","doi-asserted-by":"crossref","unstructured":"M. C. Dourado, F. Protti, and J. L. Szwarcfiter, \u201cComplexity results related to monophonic convexity,\u201d Discrete Applied Mathematics, vol. 158, no. 12, pp. 1268\u20131274, 2010.","DOI":"10.1016\/j.dam.2009.11.016"},{"key":"2024050617111940920_j_comp-2023-0103_ref_016","doi-asserted-by":"crossref","unstructured":"M. M. Kant\u00e9 and L. Nourine, \u201cPolynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs,\u201d SIAM Journal on Discrete Mathematics, vol. 30, no. 1, pp. 311\u2013326, 2016.","DOI":"10.1137\/15M1013389"},{"key":"2024050617111940920_j_comp-2023-0103_ref_017","doi-asserted-by":"crossref","unstructured":"P. Duchet, \u201cConvex sets in graphs, ii. minimal path convexity,\u201d Journal of Combinatorial Theory, Series B, vol. 44, no. 3, pp. 307\u2013316, 1988.","DOI":"10.1016\/0095-8956(88)90039-1"},{"key":"2024050617111940920_j_comp-2023-0103_ref_018","unstructured":"D. L. Kreher and D. R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search. Boca Raton: CRC Press, 1998."},{"key":"2024050617111940920_j_comp-2023-0103_ref_019","unstructured":"A. Nijenhuis and H. S. Wilf, Combinatorial Algorithms: For Computers and Calculators. New York: Academic Press, 1978."}],"container-title":["Open Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2023-0103\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2023-0103\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T17:11:32Z","timestamp":1715015492000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/comp-2023-0103\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,1]]},"references-count":19,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12,20]]},"published-print":{"date-parts":[[2023,12,20]]}},"alternative-id":["10.1515\/comp-2023-0103"],"URL":"https:\/\/doi.org\/10.1515\/comp-2023-0103","relation":{},"ISSN":["2299-1093"],"issn-type":[{"type":"electronic","value":"2299-1093"}],"subject":[],"published":{"date-parts":[[2023,1,1]]},"article-number":"20230103"}}