{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T11:03:58Z","timestamp":1775387038652,"version":"3.50.1"},"reference-count":35,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["SRG\/2023\/001592"],"award-info":[{"award-number":["SRG\/2023\/001592"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2026,5]]},"DOI":"10.1016\/j.ic.2026.105432","type":"journal-article","created":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T08:19:04Z","timestamp":1772785144000},"page":"105432","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints"],"prefix":"10.1016","volume":"310","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1073-2718","authenticated-orcid":false,"given":"Susobhan","family":"Bandopadhyay","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1761-5944","authenticated-orcid":false,"given":"Suman","family":"Banerjee","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":false,"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2026.105432_bib0001","first-page":"1","article-title":"Parameterized complexity of conflict-free matchings and paths","author":"Agrawal","year":"2020","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2026.105432_bib0002","series-title":"Combinatorial Optimization and Applications - 17Th International Conference, COCOA 2024, Beijing, China, December 6\u20138, 2024, Proceedings, Part II","first-page":"14","article-title":"Parameterized complexity of shortest path with positive disjunctive constraints","volume":"15435","author":"Bandopadhyay","year":"2024"},{"issue":"16","key":"10.1016\/j.ic.2026.105432_bib0003","doi-asserted-by":"crossref","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","article-title":"Paths, trees and matchings under disjunctive constraints","volume":"159","author":"Darmann","year":"2011","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10.1016\/j.ic.2026.105432_bib0004","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10878-011-9438-7","article-title":"The maximum flow problem with disjunctive constraints","volume":"26","author":"Pferschy","year":"2013","journal-title":"J. Comb. Optim."},{"issue":"2","key":"10.1016\/j.ic.2026.105432_bib0005","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.disopt.2010.11.001","article-title":"Online variable-sized bin packing with conflicts","volume":"8","author":"Epstein","year":"2011","journal-title":"Discrete Optim."},{"issue":"3","key":"10.1016\/j.ic.2026.105432_bib0006","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/S0305-0548(02)00195-8","article-title":"Heuristics and lower bounds for the bin packing problem with conflicts","volume":"31","author":"Gendreau","year":"2004","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"10.1016\/j.ic.2026.105432_bib0007","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1023\/A:1009871302966","article-title":"An approximation scheme for bin packing with conflicts","volume":"3","author":"Jansen","year":"1999","journal-title":"J. Comb. Optim."},{"issue":"2","key":"10.1016\/j.ic.2026.105432_bib0008","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7155\/jgaa.00186","article-title":"The knapsack problem with conflict graphs","volume":"13","author":"Pferschy","year":"2009","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"10.1016\/j.ic.2026.105432_bib0009","doi-asserted-by":"crossref","first-page":"1300","DOI":"10.1007\/s10878-016-0035-7","article-title":"Approximation of knapsack problems with conflict and forcing graphs","volume":"33","author":"Pferschy","year":"2017","journal-title":"J. Comb. Optim."},{"key":"10.1016\/j.ic.2026.105432_bib0010","series-title":"International Conference on Algorithmic Decision Theory","first-page":"414","article-title":"Determining a minimum spanning tree with disjunctive constraints","author":"Darmann","year":"2009"},{"issue":"2","key":"10.1016\/j.ic.2026.105432_bib0011","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","article-title":"Scheduling with conflicts: online and offline algorithms","volume":"12","author":"Even","year":"2009","journal-title":"J. Schedul."},{"issue":"6","key":"10.1016\/j.ic.2026.105432_bib0012","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1007\/s00224-019-09964-6","article-title":"Conflict free version of covering problems on graphs: classical and parameterized","volume":"64","author":"Jain","year":"2020","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.ic.2026.105432_bib0013","article-title":"Graph theory 3rd ed","volume":"173","author":"Diestel","year":"2005","journal-title":"Graduate Text. Math."},{"issue":"7","key":"10.1016\/j.ic.2026.105432_bib0014","doi-asserted-by":"crossref","first-page":"1612","DOI":"10.1016\/j.ejc.2009.03.014","article-title":"Vertex fusion under distance constraints","volume":"30","author":"Comas","year":"2009","journal-title":"Eur. J. Combinator."},{"issue":"10","key":"10.1016\/j.ic.2026.105432_bib0015","doi-asserted-by":"crossref","first-page":"2902","DOI":"10.1007\/s00453-020-00708-4","article-title":"On the approximate compressibility of connected vertex cover","volume":"82","author":"Majumdar","year":"2020","journal-title":"Algorithmica"},{"issue":"1","key":"10.1016\/j.ic.2026.105432_bib0016","doi-asserted-by":"crossref","DOI":"10.1016\/j.disc.2025.114699","article-title":"Vertex identification to a forest","volume":"349","author":"Morelle","year":"2024","journal-title":"Discrete Math."},{"key":"10.1016\/j.ic.2026.105432_bib0017","series-title":"Introduction to Graph Theory","author":"West","year":"2007"},{"key":"10.1016\/j.ic.2026.105432_bib0018","series-title":"Parameterized algorithms","volume":"5","author":"Cygan","year":"2015"},{"key":"10.1016\/j.ic.2026.105432_bib0019","series-title":"Parameterized complexity","author":"Downey","year":"2012"},{"issue":"1","key":"10.1016\/j.ic.2026.105432_bib0020","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","article-title":"Advice classes of parameterized tractability","volume":"84","author":"Cai","year":"1997","journal-title":"Annal. Pure Appl. Logic"},{"key":"10.1016\/j.ic.2026.105432_bib0021","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.tcs.2012.09.006","article-title":"Kernel bounds for path and cycle problems","volume":"511","author":"Bodlaender","year":"2013","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10.1016\/j.ic.2026.105432_bib0022","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/120880240","article-title":"Kernelization lower bounds by cross-Composition","volume":"28","author":"Bodlaender","year":"2014","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"10.1016\/j.ic.2026.105432_bib0023","doi-asserted-by":"crossref","first-page":"2737","DOI":"10.1137\/21M1400766","article-title":"Bridge-Depth characterizes which minor-Closed structural parameterizations of vertex cover admit a polynomial kernel","volume":"36","author":"Bougeret","year":"2022","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"10.1016\/j.ic.2026.105432_bib0024","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/2650261","article-title":"Kernelization lower bounds through colors and IDs","volume":"11","author":"Dom","year":"2014","journal-title":"ACM Trans. Algorithm."},{"key":"10.1016\/j.ic.2026.105432_bib0025","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.jcss.2022.11.002","article-title":"P-Edge\/vertex-connected vertex cover: parameterized and approximation algorithms","volume":"133","author":"Einarson","year":"2023","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1016\/j.ic.2026.105432_bib0026","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1137\/16M1088740","article-title":"Fractals for kernelization lower bounds","volume":"32","author":"Fluschnik","year":"2018","journal-title":"SIAM J. Discret. Math."},{"key":"10.1016\/j.ic.2026.105432_bib0027","series-title":"Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60Th Birthday","first-page":"18","article-title":"Hans bodlaender and the theory of kernelization lower bounds","volume":"12160","author":"Hermelin","year":"2020"},{"key":"10.1016\/j.ic.2026.105432_bib0028","series-title":"International Workshop on Parameterized and Exact Computation","first-page":"162","article-title":"A structural view on parameterizing problems: distance from triviality","author":"Guo","year":"2004"},{"key":"10.1016\/j.ic.2026.105432_bib0029","series-title":"41St International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12\u201314, 2024, Clermont-Ferrand, France","first-page":"40:1","article-title":"A faster algorithm for vertex cover parameterized by solution size","volume":"289","author":"Harris","year":"2024"},{"issue":"3","key":"10.1016\/j.ic.2026.105432_bib0030","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","article-title":"A new algorithm for generating all the maximal independent sets","volume":"6","author":"Tsukiyama","year":"1977","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/j.ic.2026.105432_bib0031","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0012-365X(89)90268-9","article-title":"On diameters and radii of bridged graphs","volume":"73","author":"Farber","year":"1989","journal-title":"Discrete Math."},{"key":"10.1016\/j.ic.2026.105432_bib0032","unstructured":"S. Dhanalakshmi, N. Sadagopan, V. Manogna, On 2K2-free graphs-structural and combinatorial view, arXiv preprint arXiv: 1602.03802(2016)."},{"issue":"3","key":"10.1016\/j.ic.2026.105432_bib0033","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","article-title":"Parameterized enumeration, transversals, and imperfect phylogeny reconstruction","volume":"351","author":"Damaschke","year":"2006","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"10.1016\/j.ic.2026.105432_bib0034","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1016\/j.jcss.2012.08.001","article-title":"Planar graph vertex partition for linear problem kernels","volume":"79","author":"Wang","year":"2013","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.ic.2026.105432_bib0035","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.tcs.2013.06.011","article-title":"Improved linear problem kernel for planar connected dominating set","volume":"511","author":"Luo","year":"2013","journal-title":"Theor. Comput. Sci."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000301?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000301?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T10:26:20Z","timestamp":1775384780000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540126000301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":35,"alternative-id":["S0890540126000301"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2026.105432","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2026,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2026.105432","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"105432"}}