Bart M. P. Jansen

Publications

My DBLP Record and Google Scholar Profile. Due to copyright restrictions, some journal articles contain improvements that are not present in the corresponding arXiv entries.

Conference publications

[1]

Lars Jaffke and Bart M. P. Jansen. “Fine-grained parameterized complexity analysis of graph coloring problems”. In: Proceedings of the 10th International Conference on Algorithms and Complexity, CIAC 2017. Volume 10236 of LNCS. 2017, pages 345–356. doi: 10.1007/978-_3- _319-_57586-_5_29. arXiv: 1701.06985.

[2]

Bart M. P. Jansen and Astrid Pieterse. “Optimal data reduction for graph coloring using low-degree polynomials”. In: Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. LIPIcs. In press. 2017, pages 1–12.

[3]

Bart M. P. Jansen and Marcin Pilipczuk. “Approximation and kernelization for chordal vertex deletion”. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. 2017, pages 1399–1418. doi: 10.1137/1.9781611974782.91. arXiv: 1605. 03001.

[4]

Bart M. P. Jansen, Marcin Pilipczuk, and Marcin Wrochna. “Turing kernelization for finding long paths in graph classes excluding a topological minor”. In: Proceedings of the 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. LIPIcs. In press. 2017. arXiv: http://arxiv.org/abs/1707.01797.

[5]

Mark de Berg, Kevin Buchin, Bart M. P. Jansen, and Gerhard Woeginger. “Fine-grained complexity analysis of two classic TSP variants”. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016. Volume 55 of Leibniz International Proceedings in Informatics (LIPIcs). 2016, 5:1–5:14. doi: 10.4230/LIPIcs.ICALP.2016.5. arXiv: 1607.02725.

[6]

Mark de Berg, Bart M. P. Jansen, and Debankur Mukherjee. “Independent-set reconfiguration thresholds of hereditary graph classes”. In: Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS. Volume 65 of LIPIcs. 2016, 34:1–34:15. doi: 10.4230/LIPIcs.FSTTCS.2016.34. arXiv: 1610.03766.

[7]

Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. “The first parameterized algorithms and computational experiments challenge”. In: Volume 63 of LIPIcs. 2016, 30:1–30:9. doi: 10.4230/LIPIcs.IPEC.2016.30.

[8]

Bart M. P. Jansen. “Constrained bipartite vertex cover: The easy kernel is essentially tight”. In: Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science, STACS 2016. Volume 47 of Leibniz International Proceedings in Informatics (LIPIcs). 2016, 45:1–45:13. doi: 10.4230/LIPIcs.STACS.2016.45.

[9]

Bart M. P. Jansen. “On structural parameterizations of hitting set: Hitting paths in graphs using 2-SAT”. In: Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015. Extended abstract of [34]. 2016, pages 472–486. doi: 10.1007/978-_3- _662-_53174-_7_33. arXiv: 1507.05890.

[10]

Bart M. P. Jansen and Astrid Pieterse. “Optimal sparsification for some binary CSPs using low-degree polynomials”. In: Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016. Volume 58 of Leibniz International Proceedings in Informatics (LIPIcs). 2016, 71:1–71:14. doi: 10.4230/LIPIcs.MFCS. 2016.71. arXiv: 1606.03233.

[11]

Bart M. P. Jansen and Jules J. M. Wulms. “Lower bounds for protrusion replacement by counting equivalence classes”. In: Proceedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC 2016. Volume 63 of LIPIcs. 2016, 17:1–17:12. doi: 10.4230/LIPIcs. IPEC.2016.17. arXiv: 1609.09304.

[12]

Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. “Uniform kernelization complexity of hitting forbidden minors”. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015. Volume 9134 of LNCS. Extended abstract of [33]. 2015, pages 629–641. doi: 10.1007/978- _3-_662-_47672-_7_51. arXiv: 1502.03965.

[13]

Bart M. P. Jansen and Stefan Kratsch. “A structural approach to kernels for ILPs: Treewidth and total unimodularity”. In: Proceedings of the 23rd European Symposium on Algorithms, ESA 2015. Volume 9294 of LNCS. 2015, pages 779–791. doi: 10.1007/978-_3-_662-_48350-_3_65. arXiv: 1506.07729.

[14]

Bart M. P. Jansen and Dániel Marx. “Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels”. In: Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. 2015, pages 616–629. doi: 10.1137/1. 9781611973730.42. arXiv: 1410.0855.

[15]

Bart M. P. Jansen and Astrid Pieterse. “Sparsification upper and lower bounds for graph problems and not-all-equal SAT”. In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Volume 43 of LIPIcs. Extended abstract of [36]. 2015, pages 163–174. doi: 10.4230/LIPIcs.IPEC.2015.163. arXiv: 1509. 07437.

[16]

Bart M. P. Jansen. “Turing kernelization for finding long paths and cycles in restricted graph classes”. In: Proceedings of the 22nd European Symposium on Algorithms, ESA 2014. Volume 8737 of LNCS. Extended abstract of [35]. 2014, pages 579–591. doi: 10.1007/978-_3-_662- _44777-_2_48. arXiv: 1402.4718.

[17]

Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. “A near-optimal planarization algorithm”. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. 2014, pages 1802–1811. doi: 10.1137/1.9781611973402.130.

[18]

Michael R. Fellows and Bart M. P. Jansen. “FPT is characterized by useful obstruction sets”. In: Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013. Volume 8165 of LNCS. Extended abstract of [39]. 2013, pages 261–273. doi: 10.1007/ 978-_3-_642-_45043-_3_23. arXiv: 1305.3102.

[19]

Bart M. P. Jansen. “On sparsification for computing treewidth”. In: Proceedings of the 8th International Symposium on Parameterized and Exact Computation, IPEC 2013. Volume 8246 of LNCS. Excellent Student Paper Award Winner. Extended abstract of [37]. 2013, pages 216–229. doi: 10.1007/978-_3-_319-_03898-_8_19. arXiv: 1308.3665.

[20]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernel bounds for structural parameterizations of pathwidth”. In: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012. Volume 7357 of LNCS. 2012, pages 352–363. doi: 10.1007/ 978-_3-_642-_31155-_0_31. arXiv: 1207.4900.

[21]

Fedor V. Fomin, Bart M. P. Jansen, and Michal Pilipczuk. “Preprocessing subgraph and minor problems: When does a small vertex cover help?” In: Proceedings of the 7th International Symposium on Parameterized and Exact Computation, IPEC 2012. Volume 7535 of LNCS. Extended abstract of [40]. 2012, pages 97–108. doi: 10.1007/978-_3-_642-_33293- _7_11. arXiv: 1206.4912.

[22]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Cross-composition: A new technique for kernelization lower bounds”. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. Volume 9 of LIPIcs. Open Access, Extended abstract of [38]. 2011, pages 165–176. doi: 10.4230/LIPIcs. STACS.2011.165. arXiv: 1011.4224.

[23]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernel bounds for path and cycle problems”. In: Proceedings of the 6th International Symposium on Parameterized and Exact Computation, IPEC 2011. Volume 7112 of LNCS. Extended abstract of [42]. 2011, pages 145–158. doi: 10.1007/978-_3-_642-_28050-_4_12. arXiv: 1106.4141.

[24]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Preprocessing for treewidth: A combinatorial analysis through kernelization”. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011. Volume 6755 of LNCS. Extended abstract of [43]. 2011, pages 437–448. doi: 10.1007/978- _3-_642-_22006-_7_37. arXiv: 1104.4217.

[25]

Pinar Heggernes, Pim van ’t Hof, Bart M. P. Jansen, Stefan Kratsch, and Yngve Villanger. “Parameterized complexity of vertex deletion into perfect graph classes”. In: Proceedings of the 18th International Symposium on Fundamentals of Computation Theory, FCT 2011. Volume 6914 of LNCS. Extended abstract of [45]. 2011, pages 240–251. doi: 10. 1007/978-_3-_642-_22953-_4_21.

[26]

Bart M. P. Jansen and Hans L. Bodlaender. “Vertex cover kernelization revisited: Upper and lower bounds for a refined parameter”. In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011. Volume 9 of LIPIcs. Open Access, Extended abstract of [46]. 2011, pages 177–188. doi: 10.4230/LIPIcs. STACS.2011.177. arXiv: 1012.4701.

[27]

Bart M. P. Jansen and Stefan Kratsch. “Data reduction for graph coloring problems”. In: Proceedings of the 18th International Symposium on Fundamentals of Computation Theory, FCT 2011. Volume 6914 of LNCS. Extended Abstract of [47]. 2011, pages 90–101. doi: 10.1007/978- _3-_642-_22953-_4_8. arXiv: 1104.4229.

[28]

Bart M. P. Jansen and Stefan Kratsch. “On polynomial kernels for structural parameterizations of odd cycle transversal”. In: Proceedings of the 6th International Symposium on Parameterized and Exact Computation, IPEC 2011. Volume 7112 of LNCS. 2011, pages 132–144. doi: 10.1007/978-_3-_642-_28050-_4_11. arXiv: 1107.3658.

[29]

Michael R. Fellows, Bart M. P. Jansen, Daniel Lokshtanov, Frances A. Rosamond, and Saket Saurabh. “Determining the winner of a Dodgson election is hard”. In: Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010. Volume 8 of LIPIcs. Open Access. 2010, pages 459–468. doi: 10.4230/LIPIcs.FSTTCS.2010.459.

[30]

Bart M. P. Jansen. “Kernelization for maximum leaf spanning tree with positive vertex weights”. In: Proceedings of the 7th International Conference on Algorithms and Complexity, CIAC 2010. Volume 6078 of LNCS. Extended abstract of [48]. 2010, pages 192–203. doi: 10.1007/978- _3-_642-_13073-_1_18.

[31]

Bart M. P. Jansen. “Polynomial kernels for hard problems on disk graphs”. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2010. Volume 6139 of LNCS. 2010, pages 310–321. doi: 10.1007/978-_3-_642-_13731-_0_30. url: https://www.win.tue.nl/~bjansen/papers/DiskGraphsPreprint.pdf.

[32]

Boris Aronov, Kevin Buchin, Maike Buchin, Bart M. P. Jansen, T. de Jong, Marc J. van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira, and Bettina Speckmann. “Feed-links for network extensions”. In: Proceedings of the 16th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2008. Extended abstract of [49]. 2008, pages 1–9. doi: 10.1145/1463434.1463478.

Journal publications

[33]

Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. “Uniform kernelization complexity of hitting forbidden minors”. In: ACM Trans. Algorithms 13(3), 2017, 35:1–35:35. doi: 10. 1145/3029051. arXiv: 1502.03965.

[34]

Bart M. P. Jansen. “On structural parameterizations of hitting set: Hitting paths in graphs using 2-SAT”. In: Journal of Graph Algorithms and Applications 21(2), 2017, pages 219–243. doi: 10.7155/jgaa.00413.

[35]

Bart M. P. Jansen. “Turing kernelization for finding long paths and cycles in restricted graph classes”. In: Journal of Computer and System Sciences 85, 2017, pages 18–37. doi: 10.1016/j.jcss.2016.10.008.

[36]

Bart M. P. Jansen and Astrid Pieterse. “Sparsification upper and lower bounds for graph problems and not-all-equal SAT”. In: Algorithmica, 2016. IPEC 2015 Special Issue (Online first), pages 1–26. doi: 10.1007/s00453- _016-_0189-_9. arXiv: 1509.07437.

[37]

Bart M. P. Jansen. “On sparsification for computing treewidth”. In: Algorithmica 71(3), 2015. IPEC 2013 Special Issue, pages 605–635. doi: 10.1007/s00453-_014-_9924-_2. arXiv: 1308.3665.

[38]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernelization lower bounds by cross-composition”. In: SIAM Journal on Discrete Mathematics 28(1), 2014, pages 277–305. doi: 10.1137/ 120880240. arXiv: 1206.5941.

[39]

Michael R. Fellows and Bart M. P. Jansen. “FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders”. In: ACM Transactions on Computation Theory 6(4), 2014, 16:1–16:26. doi: 10.1145/2635820. arXiv: 1305.3102.

[40]

Fedor V. Fomin, Bart M. P. Jansen, and Michal Pilipczuk. “Preprocessing subgraph and minor problems: When does a small vertex cover help?” In: Journal of Computer and System Sciences 80(2), 2014, pages 468–495. doi: 10.1016/j.jcss.2013.09.004.

[41]

Bart M. P. Jansen, Venkatesh Raman, and Martin Vatshelle. “Parameter ecology for feedback vertex set”. In: Tsinghua Science and Technology 19(4), 2014. Special Issue dedicated to Jianer Chen, pages 387–409. doi: 10.1109/TST.2014.6867520.

[42]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Kernel bounds for path and cycle problems”. In: Theoretical Computer Science 511, 2013. Special Issue on Parameterized and Exact Computation, pages 117–136. doi: 10.1016/j.tcs.2012.09.006. arXiv: 1106.4141.

[43]

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. “Preprocessing for treewidth: A combinatorial analysis through kernelization”. In: SIAM Journal on Discrete Mathematics 27(4), 2013, pages 2108–2142. doi: 10.1137/120903518. arXiv: 1104.4217.

[44]

Michael R. Fellows, Bart M. P. Jansen, and Frances Rosamond. “Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity”. In: European Journal of Combinatorics 34(3), 2013. IWOCA 2009 Special Issue, pages 541–566. doi: 10 . 1016 / j . ejc . 2012 . 04 . 008. url: https://www.win.tue.nl/~bjansen/papers/EcologySurvey.pdf.

[45]

Pinar Heggernes, Pim van ’t Hof, Bart M. P. Jansen, Stefan Kratsch, and Yngve Villanger. “Parameterized complexity of vertex deletion into perfect graph classes”. In: Theoretical Computer Science 511, 2013. Special Issue on Parameterized and Exact Computation, pages 172–180. doi: 10 . 1016 / j . tcs . 2012 . 03 . 013. url: https://www.win.tue.nl/~bjansen/papers/PerfectDeletion.pdf.

[46]

Bart M. P. Jansen and Hans L. Bodlaender. “Vertex cover kernelization revisited - Upper and lower bounds for a refined parameter”. In: Theory of Computing Systems 53(2), 2013. Open Access, STACS 2011 Special Issue, pages 263–299. doi: 10.1007/s00224-_012-_9393-_4.

[47]

Bart M. P. Jansen and Stefan Kratsch. “Data reduction for graph coloring problems”. In: Information and Computation 231, 2013. FCT 2011 Special Issue, pages 70–88. doi: 10.1016/j.ic.2013.08.005. arXiv: 1104.4229.

[48]

Bart M. P. Jansen. “Kernelization for maximum leaf spanning tree with positive vertex weights”. In: Journal of Graph Algorithms and Applications 16(4), 2012. Open Access, pages 811–846. doi: 10.7155/ jgaa.00279.

[49]

Boris Aronov, Kevin Buchin, Maike Buchin, Bart M. P. Jansen, Tom de Jong, Marc J. van Kreveld, Maarten Löffler, Jun Luo, Rodrigo I. Silveira, and Bettina Speckmann. “Connect the dot: Computing feed-links for network extension”. In: Journal of Spatial Information Science 3(1), 2011. Open Access, pages 3–31. doi: 10.5311/JOSIS.2011.3.47.

Popular science

[50]

De Kennis van Nu Radio (Interview). Dutch. Interview about my Ph. D. thesis after winning the Huygens Prize. Interview starts at 45:20. June 30, 2014. url: http://www.wetenschap24.nl/programmas/de-_kennis-_van-_nu/Radio-_5/2014/Juni/30-_06-_2014-_Big-_Data-_in-_de-_stad.html.

[51]

Joost Hanraets and Bart M. P. Jansen. Met reductieregels grote datasets te lijf. Dutch. Interview about my Ph. D. thesis after winning the Huygens Prize. 2014. url: http://public.dhe.ibm.com/common/ssi/ecm/nl/xi103015nlnl/XI103015NLNL.PDF.

De Kennis van Nu Radio (Interview). Dutch. Interview about my Ph. D. thesis after winning the Huygens Prize. Interview starts at 45:20. June 30, 2014. url: http://www.wetenschap24.nl/programmas/de-_kennis-_van-_nu/Radio-_5/2014/Juni/30-_06-_2014-_Big-_Data-_in-_de-_stad.html.

[49]

Joost Hanraets and Bart M. P. Jansen. Met reductieregels grote datasets te lijf. Dutch. Interview about my Ph. D. thesis after winning the Huygens Prize. 2014. url: http://public.dhe.ibm.com/common/ssi/ecm/nl/xi103015nlnl/XI103015NLNL.PDF.

Ph.D. Thesis

  • Bart M. P. Jansen. "The Power of Data Reduction: Kernels for Fundamental Graph Problems". Utrecht University, 2013, 310 pages, ISBN 978-90-393-5966-2, PDF, Info

Master's Thesis

  • Bart M. P. Jansen: Fixed Parameter Complexity of the Weighted Max Leaf Problem, Master Thesis INF/SCR-2008-075, Utrecht University, 2009, PDF, Info