{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T06:50:54Z","timestamp":1770619854946,"version":"3.49.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T00:00:00Z","timestamp":1611187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Royal Society Wolfson Research Merit Award and Leverhulme Trust","award":["RPG-2018-161"],"award-info":[{"award-number":["RPG-2018-161"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,1,31]]},"abstract":"<jats:p>\n            Abasi et al. (2014) introduced the following two problems. In the\n            <jats:italic>r<\/jats:italic>\n            -S\n            <jats:sc>imple<\/jats:sc>\n            <jats:italic>k<\/jats:italic>\n            -P\n            <jats:sc>ath<\/jats:sc>\n            problem, given a digraph\u00a0\n            <jats:italic>G<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            \u00a0vertices and positive integers\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            , decide whether\n            <jats:italic>G<\/jats:italic>\n            has an\n            <jats:italic>r<\/jats:italic>\n            -simple\n            <jats:italic>k<\/jats:italic>\n            -path, which is a walk where every vertex occurs at most\n            <jats:italic>r<\/jats:italic>\n            times and the total number of vertex occurrences is\n            <jats:italic>k<\/jats:italic>\n            . In the (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            problem, given an arithmetic circuit that succinctly encodes some polynomial\n            <jats:italic>P<\/jats:italic>\n            on\n            <jats:italic>n<\/jats:italic>\n            variables and positive integers\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>r<\/jats:italic>\n            , decide whether\n            <jats:italic>P<\/jats:italic>\n            has a monomial of total degree\n            <jats:italic>k<\/jats:italic>\n            where the degree of each variable is at most\u00a0\n            <jats:italic>r<\/jats:italic>\n            . Abasi et al.\u00a0obtained randomized algorithms of running time 4\n            <jats:sup>\n              (\n              <jats:italic>k<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              )log\n              <jats:italic>r<\/jats:italic>\n            <\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            for both problems. Gabizon et al.\u00a0(2015) designed deterministic 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              ((\n              <jats:italic>k<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              )log\n              <jats:italic>r<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -time algorithms for both problems (however, for the (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            problem the input circuit is restricted to be non-canceling). Gabizon et al.\u00a0also studied the following problem. In the\n            <jats:italic>P<\/jats:italic>\n            -S\n            <jats:sc>et<\/jats:sc>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )-P\n            <jats:sc>acking<\/jats:sc>\n            P\n            <jats:sc>roblem<\/jats:sc>\n            , given a universe\n            <jats:italic>V<\/jats:italic>\n            , positive integers (\n            <jats:italic>p<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            ,\n            <jats:italic>r<\/jats:italic>\n            ), and a collection H of sets of size\n            <jats:italic>P<\/jats:italic>\n            whose elements belong to\n            <jats:italic>V<\/jats:italic>\n            , decide whether there exists a subcollection H\n            <jats:sup>\u2032<\/jats:sup>\n            of H of size\n            <jats:italic>q<\/jats:italic>\n            where each element occurs in at most\n            <jats:italic>r<\/jats:italic>\n            sets of H\n            <jats:sup>\u2032<\/jats:sup>\n            . Gabizon et al.\u00a0obtained a deterministic 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              ((\n              <jats:italic>pq<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              )log\n              <jats:italic>r<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -time algorithm for\n            <jats:italic>P<\/jats:italic>\n            -S\n            <jats:sc>et<\/jats:sc>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )-P\n            <jats:sc>acking<\/jats:sc>\n            .\n          <\/jats:p>\n          <jats:p>\n            The above results prove that the three problems are\n            <jats:italic>single-exponentially<\/jats:italic>\n            fixed-parameter tractable (FPT) parameterized by the product of\n            <jats:italic>two<\/jats:italic>\n            parameters, that is,\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            and log\n            <jats:italic>r<\/jats:italic>\n            , where\n            <jats:italic>k<\/jats:italic>\n            =\n            <jats:italic>pq<\/jats:italic>\n            for\n            <jats:italic>P<\/jats:italic>\n            -S\n            <jats:sc>et<\/jats:sc>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )-P\n            <jats:sc>acking<\/jats:sc>\n            . Abasi et al.\u00a0and Gabizon et al.\u00a0asked whether the log\n            <jats:italic>r<\/jats:italic>\n            factor in the exponent can be avoided. Bonamy et al.\u00a0(2017) answered the question for (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            by proving that unless the Exponential Time Hypothesis (ETH) fails there is no 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              ((\n              <jats:italic>k<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              ) log\n              <jats:italic>r<\/jats:italic>\n              )\n            <\/jats:sup>\n            \u22c5 (\n            <jats:italic>n<\/jats:italic>\n            + log\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -time algorithm for (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            , i.e., (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            is unlikely to be single-exponentially FPT when parameterized by\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            alone. The question remains open for\n            <jats:italic>r<\/jats:italic>\n            -S\n            <jats:sc>imple<\/jats:sc>\n            <jats:italic>k<\/jats:italic>\n            -P\n            <jats:sc>ath<\/jats:sc>\n            and\n            <jats:italic>P<\/jats:italic>\n            -S\n            <jats:sc>et<\/jats:sc>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )-P\n            <jats:sc>acking<\/jats:sc>\n            .\n          <\/jats:p>\n          <jats:p>\n            We consider the question from a wider perspective: are the above problems FPT when parameterized by\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            only, i.e., whether there exists a computable function\n            <jats:italic>f<\/jats:italic>\n            such that the problems admit a\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            )(\n            <jats:italic>n<\/jats:italic>\n            +log\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -time algorithm? Since\n            <jats:italic>r<\/jats:italic>\n            can be substantially larger than the input size, the algorithms of Abasi et al.\u00a0and Gabizon et al. do not even show that any of these three problems is in XP parameterized by\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            alone. We resolve the wider question by (a) obtaining a 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              ((\n              <jats:italic>k<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              )\n            <\/jats:sup>\n            <jats:sup>2<\/jats:sup>\n            <jats:sup>\n              log(\n              <jats:italic>k<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              ))\n            <\/jats:sup>\n            \u22c5 (\n            <jats:italic>n<\/jats:italic>\n            + log\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -time algorithm for\n            <jats:italic>r<\/jats:italic>\n            -S\n            <jats:sc>imple<\/jats:sc>\n            <jats:italic>k<\/jats:italic>\n            -P\n            <jats:sc>ath<\/jats:sc>\n            on digraphs and a 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              \/\n              <jats:italic>r<\/jats:italic>\n              )\n            <\/jats:sup>\n            &amp;sdot (\n            <jats:italic>n<\/jats:italic>\n            + log\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -time algorithm for\n            <jats:italic>r<\/jats:italic>\n            -S\n            <jats:sc>imple<\/jats:sc>\n            <jats:italic>k<\/jats:italic>\n            -P\n            <jats:sc>ath<\/jats:sc>\n            on undirected graphs (i.e., for undirected graphs, we answer the original question in affirmative), (b) showing that\n            <jats:italic>P<\/jats:italic>\n            -S\n            <jats:sc>et<\/jats:sc>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )-P\n            <jats:sc>acking<\/jats:sc>\n            is FPT (in contrast, we prove that\n            <jats:italic>P<\/jats:italic>\n            -M\n            <jats:sc>ultiset<\/jats:sc>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )-P\n            <jats:sc>acking<\/jats:sc>\n            is W[1]-hard), and (c) proving that (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            is para-NP-hard even if only two distinct variables are in polynomial\n            <jats:italic>P<\/jats:italic>\n            and the circuit is non-canceling. For the special case of (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-M\n            <jats:sc>onomial<\/jats:sc>\n            D\n            <jats:sc>etection<\/jats:sc>\n            where\n            <jats:italic>k<\/jats:italic>\n            is polynomially bounded by the input size (which is in XP), we show W[1]-hardness. Along the way to solve\n            <jats:italic>P<\/jats:italic>\n            -S\n            <jats:sc>et<\/jats:sc>\n            (\n            <jats:italic>r<\/jats:italic>\n            ,\n            <jats:italic>q<\/jats:italic>\n            )-P\n            <jats:sc>acking<\/jats:sc>\n            , we obtain a polynomial kernel for any fixed\n            <jats:italic>P<\/jats:italic>\n            , which resolves a question posed by Gabizon et al.\u00a0regarding the existence of polynomial kernels for problems with relaxed disjointness constraints. All our algorithms are deterministic.\n          <\/jats:p>","DOI":"10.1145\/3439721","type":"journal-article","created":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T17:23:29Z","timestamp":1611249809000},"page":"1-64","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["<i>r<\/i>\n            -Simple\n            <i>k<\/i>\n            -Path and Related Problems Parameterized by\n            <i>k<\/i>\n            \/\n            <i>r<\/i>"],"prefix":"10.1145","volume":"17","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magnus","family":"Wahlstr\u00f6m","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, Egham, Surrey, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beersheba, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,1,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1136614"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/137406"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9428-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186897"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1523254"},{"key":"e_1_2_1_8_1","first-page":"48350","volume-title":"Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915)","volume":"9294","author":"Bansal Nikhil","year":"2015","unstructured":"Nikhil Bansal and Irene Finocchi ( Eds .). 2015 . Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915) . Lecture Notes in Computer Science , Vol. 9294 . Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-662- 48350 - 48353 10.1007\/978-3-662-48350-3 Nikhil Bansal and Irene Finocchi (Eds.). 2015. Proceedings of the 23rd Annual European Symposium on Algorithms (ESA\u201915). Lecture Notes in Computer Science, Vol. 9294. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-662-48350-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310541"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.03.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1048975"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313906"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095122"},{"key":"e_1_2_1_18_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2016. Graph Theory , 5 th ed. Graduate texts in mathematics, Vol. 173 . Springer . Reinhard Diestel. 2016. Graph Theory, 5th ed. Graduate texts in mathematics, Vol. 173. Springer.","edition":"5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2568438"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786015"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1121738"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.04.018"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_2_1_27_1","first-page":"545","volume-title":"Fast algorithms for parameterized problems with relaxed disjointness constraints","author":"Gabizon Ariel","unstructured":"Ariel Gabizon , Daniel Lokshtanov , and Michal Pilipczuk . 2015. Fast algorithms for parameterized problems with relaxed disjointness constraints ; see Reference Bansal and Finocchi [8], pp. 545 -- 556 . DOI:https:\/\/doi.org\/10.1007\/978-3-662-48350-3_46 10.1007\/978-3-662-48350-3_46 Ariel Gabizon, Daniel Lokshtanov, and Michal Pilipczuk. 2015. Fast algorithms for parameterized problems with relaxed disjointness constraints; see Reference Bansal and Finocchi [8], pp. 545--556. DOI:https:\/\/doi.org\/10.1007\/978-3-662-48350-3_46"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.01.004"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634205"},{"key":"e_1_2_1_32_1","volume-title":"Lecture Notes in Computer Science","author":"Kloks Ton","unstructured":"Ton Kloks . 1994. Treewidth, Computations and Approximations . Lecture Notes in Computer Science , Vol. 842 . Springer . Ton Kloks. 1994. Treewidth, Computations and Approximations. Lecture Notes in Computer Science, Vol. 842. Springer."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2885499"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118500053"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 6th British Combinatorial Conference (CombinatorialSurveys\u201977)","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1977","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1977 . Flats in matroids and geometric graphs . In Proceedings of the 6th British Combinatorial Conference (CombinatorialSurveys\u201977) . Academic Press, 45--86. L\u00e1szl\u00f3 Lov\u00e1sz. 1977. Flats in matroids and geometric graphs. In Proceedings of the 6th British Combinatorial Conference (CombinatorialSurveys\u201977). Academic Press, 45--86."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34611-8_19"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00078-3"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 8th International Workshop on Algorithms and Computation (WALCOM\u201914)","volume":"8344","author":"Romero Jazm\u00edn","year":"2014","unstructured":"Jazm\u00edn Romero and Alejandro L\u00f3pez-Ortiz . 2014 . The G -packing with t-overlap problem . In Proceedings of the 8th International Workshop on Algorithms and Computation (WALCOM\u201914) (Lecture Notes in Computer Science), Sudebkumar Prasant Pal and Kunihiko Sadakane (Eds.) , Vol. 8344 . Springer, 114--124. DOI:https:\/\/doi.org\/10.1007\/978-3-319-04657-0_13 10.1007\/978-3-319-04657-0_13 Jazm\u00edn Romero and Alejandro L\u00f3pez-Ortiz. 2014. The G -packing with t-overlap problem. In Proceedings of the 8th International Workshop on Algorithms and Computation (WALCOM\u201914) (Lecture Notes in Computer Science), Sudebkumar Prasant Pal and Kunihiko Sadakane (Eds.), Vol. 8344. Springer, 114--124. DOI:https:\/\/doi.org\/10.1007\/978-3-319-04657-0_13"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06686-8_25"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.008"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120111"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"e_1_2_1_47_1","first-page":"1037","volume-title":"Mixing color coding-related techniques","author":"Zehavi Meirav","unstructured":"Meirav Zehavi . 2015. Mixing color coding-related techniques ; see Reference Bansal and Finocchi [8], pp. 1037 -- 1049 . DOI:https:\/\/doi.org\/10.1007\/978-3-662-48350-3_86 10.1007\/978-3-662-48350-3_86 Meirav Zehavi. 2015. Mixing color coding-related techniques; see Reference Bansal and Finocchi [8], pp. 1037--1049. DOI:https:\/\/doi.org\/10.1007\/978-3-662-48350-3_86"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.02.005"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3439721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:52Z","timestamp":1750197712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3439721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,21]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1,31]]}},"alternative-id":["10.1145\/3439721"],"URL":"https:\/\/doi.org\/10.1145\/3439721","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,21]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}