{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T06:02:54Z","timestamp":1746252174745,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T00:00:00Z","timestamp":1581292800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100009328","name":"Planning and Budgeting Committee of the Council for Higher Education of Israel","doi-asserted-by":"publisher","award":["5101479000"],"award-info":[{"award-number":["5101479000"]}],"id":[{"id":"10.13039\/501100009328","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["PDF\/2016\/003508"],"award-info":[{"award-number":["PDF\/2016\/003508"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s00453-020-00681-y","type":"journal-article","created":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T13:03:03Z","timestamp":1581339783000},"page":"1939-1965","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Parameterized Complexity of Conflict-Free Matchings and Paths"],"prefix":"10.1007","volume":"82","author":[{"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[]},{"given":"Pallavi","family":"Jain","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9274-4119","authenticated-orcid":false,"given":"Lawqueen","family":"Kanesh","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,10]]},"reference":[{"key":"681_CR1","unstructured":"Agrawal, A., Jain, P., Kanesh, L., Lokshtanov, D., Saurabh, S.: Conflict free feedback vertex set: a parameterized dichotomy. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS) pp. 53:1\u201353:15 (2018)"},{"key":"681_CR2","unstructured":"Agrawal, A., Jain, P., Kanesh, L., Misra, P., Saurabh, S.: Exploring the kernelization borders for hitting cycles. In: 13th International Symposium on Parameterized and Exact Computation (IPEC) pp. 14:1\u201314:14 (2018)"},{"issue":"1","key":"681_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Q. Appl. Math. 16(1), 87\u201390 (1958)","journal-title":"Q. Appl. Math."},{"key":"681_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"681_CR5","doi-asserted-by":"crossref","unstructured":"Darmann, A., Pferschy, U., Schauer, J.: Determining a minimum spanning tree with disjunctive constraints. In: International Conference on Algorithmic Decision Theory (ADT), pp. 414\u2013423 (2009)","DOI":"10.1007\/978-3-642-04428-1_36"},{"issue":"16","key":"681_CR6","doi-asserted-by":"crossref","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","volume":"159","author":"A Darmann","year":"2011","unstructured":"Darmann, A., Pferschy, U., Schauer, J., Woeginger, G.J.: Paths, trees and matchings under disjunctive constraints. Discrete Appl. Math. 159(16), 1726\u20131735 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"681_CR7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische mathematik 1(1), 269\u2013271 (1959)","journal-title":"Numerische mathematik"},{"issue":"1\u20132","key":"681_CR8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W [1]. Theor. Comput. Sci. 141(1\u20132), 109\u2013131 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"681_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"issue":"2","key":"681_CR10","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.disopt.2010.11.001","volume":"8","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Favrholdt, L.M., Levin, A.: Online variable-sized bin packing with conflicts. Discrete Optim. 8(2), 333\u2013343 (2011)","journal-title":"Discrete Optim."},{"issue":"2","key":"681_CR11","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even, G., Halld\u00f3rsson, M.M., Kaplan, L., Ron, D.: Scheduling with conflicts: online and offline algorithms. J. Sched. 12(2), 199\u2013224 (2009)","journal-title":"J. Sched."},{"key":"681_CR12","doi-asserted-by":"crossref","unstructured":"Even, S., Kariv, O.: An $${O}(n^{2.5})$$ algorithm for maximum matching in general graphs. In: Foundations of Computer Science (FOCS), pp. 100\u2013112 (1975)","DOI":"10.1109\/SFCS.1975.5"},{"key":"681_CR13","volume-title":"Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer, Secaucus (2006)"},{"issue":"4","key":"681_CR14","doi-asserted-by":"crossref","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016)","journal-title":"J. ACM"},{"key":"681_CR15","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Efficient computation of representative sets with applications in parameterized and exact algorithms. In: Symposium on Discrete Algorithms (SODA), pp. 142\u2013151 (2014)","DOI":"10.1137\/1.9781611973402.10"},{"issue":"3","key":"681_CR16","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1109\/TSE.1976.233819","volume":"2","author":"HN Gabow","year":"1976","unstructured":"Gabow, H.N., Maheshwari, S.N., Osterweil, L.J.: On two problems in the generation of program test paths. IEEE Trans. Softw. Eng. 2(3), 227\u2013231 (1976)","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"1","key":"681_CR17","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"681_CR18","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/S0305-0548(02)00195-8","volume":"31","author":"M Gendreau","year":"2004","unstructured":"Gendreau, M., Laporte, G., Semet, F.: Heuristics and lower bounds for the bin packing problem with conflicts. Comput. OR 31(3), 347\u2013358 (2004)","journal-title":"Comput. OR"},{"key":"681_CR19","doi-asserted-by":"crossref","unstructured":"Jain, P., Kanesh, L., Misra, P.: Conflict free version of covering problems on graphs: classical and parameterized. In: Computer Science\u2014Theory and Applications\u201413th International Computer Science Symposium in Russia (CSR), pp. 194\u2013206 (2018)","DOI":"10.1007\/978-3-319-90530-3_17"},{"issue":"4","key":"681_CR20","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1023\/A:1009871302966","volume":"3","author":"K Jansen","year":"1999","unstructured":"Jansen, K.: An approximation scheme for bin packing with conflicts. J. Comb. Optim. 3(4), 363\u2013377 (1999)","journal-title":"J. Comb. Optim."},{"issue":"49","key":"681_CR21","doi-asserted-by":"crossref","first-page":"4253","DOI":"10.1016\/j.tcs.2010.09.001","volume":"411","author":"M Jiang","year":"2010","unstructured":"Jiang, M.: On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theor. Comput. Sci. 411(49), 4253\u20134262 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"681_CR22","volume-title":"Treewidth, Computations and Approximations, Lecture Notes in Computer Science","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations, Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)"},{"key":"681_CR23","volume-title":"Optimal software test planning through automated network analysis","author":"K Krause","year":"1973","unstructured":"Krause, K., Goodwin, M., Smith, R.: Optimal software test planning through automated network analysis. TRW Systems Group, Euclid (1973)"},{"key":"681_CR24","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.: Deterministic truncation of linear matroids. In: International Colloquium on Automata, Languages, and Programming (ICALP), pp. 922\u2013934 (2015)","DOI":"10.1007\/978-3-662-47672-7_75"},{"key":"681_CR25","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Saurabh, S., Sharma, R., Zehavi, M.: Covering small independent sets and separators with applications to parameterized algorithms. In: Symposium on Discrete Algorithms (SODA), pp. 2785\u20132800 (2018)","DOI":"10.1137\/1.9781611975031.177"},{"issue":"44","key":"681_CR26","doi-asserted-by":"crossref","first-page":"4471","DOI":"10.1016\/j.tcs.2009.07.027","volume":"410","author":"D Marx","year":"2009","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471\u20134479 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"681_CR27","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.V.: An $$O(\\sqrt{|}V||E|)$$ algorithm for finding maximum matching in general graphs. In: Foundations of Computer Science (FOCS), pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"681_CR28","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Foundations of Computer Science (FOCS), pp. 182\u2013191 (1995)"},{"key":"681_CR29","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"key":"681_CR30","volume-title":"Matroid Theory","author":"JG Oxley","year":"2006","unstructured":"Oxley, J.G.: Matroid Theory, vol. 3. Oxford University Press, Oxford (2006)"},{"issue":"2","key":"681_CR31","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233\u2013249 (2009)","journal-title":"J. Graph Algorithms Appl."},{"key":"681_CR32","doi-asserted-by":"crossref","unstructured":"Pferschy, U., Schauer, J.: The maximum flow problem with conflict and forcing conditions. In: International Conference on Network Optimization, pp. 289\u2013294 (2011)","DOI":"10.1007\/978-3-642-21527-8_34"},{"issue":"1","key":"681_CR33","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10878-011-9438-7","volume":"26","author":"U Pferschy","year":"2013","unstructured":"Pferschy, U., Schauer, J.: The maximum flow problem with disjunctive constraints. J. Comb. Optim. 26(1), 109\u2013119 (2013)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"681_CR34","doi-asserted-by":"crossref","first-page":"1300","DOI":"10.1007\/s10878-016-0035-7","volume":"33","author":"U Pferschy","year":"2017","unstructured":"Pferschy, U., Schauer, J.: Approximation of knapsack problems with conflict and forcing graphs. J. Comb. Optim. 33(4), 1300\u20131323 (2017)","journal-title":"J. Comb. Optim."},{"key":"681_CR35","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Symposium on Theory of Computing (STOC), pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00681-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00681-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00681-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T23:41:32Z","timestamp":1612914092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00681-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,10]]},"references-count":35,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["681"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00681-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,2,10]]},"assertion":[{"value":"10 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}