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.

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

Conference publications

[1]

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.

[2]

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 [30]. 2013, pages 261–273. doi: 10.1007/ 978-3-642-45043-3_23. arXiv: 1305.3102.

[3]

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 [31]. 2013, pages 216–229. doi: 10.1007/978-3-319-03898-8_19. arXiv: 1308.3665.

[4]

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.

[5]

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 [21]. 2012, pages 97–108. doi: 10.1007/978-3-642-33293- 7_11. arXiv: 1206.4912.

[6]

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 [20]. 2011, pages 165–176. doi: 10.4230/LIPIcs. STACS.2011.165. arXiv: 1011.4224.

[7]

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 [22]. 2011, pages 145–158. doi: 10.1007/978-3-642-28050-4_12. arXiv: 1106. 4141.

[8]

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 [23]. 2011, pages 437–448. doi: 10.1007/978- 3-642-22006-7_37. arXiv: 1104.4217.

[9]

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 [25]. 2011, pages 240–251. doi: 10. 1007/978-3-642-22953-4_21.

[10]

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 [26]. 2011, pages 177–188. doi: 10.4230/LIPIcs. STACS.2011.177. arXiv: 1012.4701.

[11]

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 [27]. 2011, pages 90–101. doi: 10.1007/978- 3-642-22953-4_8. arXiv: 1104.4229.

[12]

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.

[13]

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.

[14]

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 [28]. 2010, pages 192–203. doi: 10.1007/978- 3-642-13073-1_18.

[15]

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: http://people.uib.no/bja065/papers/DiskGraphsPreprint.pdf.

[16]

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 [29]. 2008, pages 1–9. doi: 10.1145/1463434.1463478.

Conference submissions

[17]

Bart M. P. Jansen. Turing Kernelization for Finding Long Paths and Cycles in Restricted Graph Classes. 23 pages, submitted to ESA. 2014. arXiv: 1402.4718.

[18]

Bart M. P. Jansen and Stefan Kratsch. Preprocessing for Integer Linear Programs: Treewidth and Total Unimodularity. 23 pages, submitted to ESA. 2014.

[19]

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. 73 pages, submitted to FOCS. 2014.

Journal publications

[20]

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.

[21]

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.

[22]

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.

[23]

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.

[24]

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: http://people.uib.no/bja065/papers/EcologySurvey.pdf.

[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: Theoretical Computer Science 511, 2013. Special Issue on Parameterized and Exact Computation, pages 172–180. doi: 10 . 1016 / j . tcs . 2012 . 03 . 013. url: http://people.uib.no/bja065/papers/PerfectDeletion.pdf.

[26]

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.

[27]

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.

[28]

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.

[29]

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.

Journal submissions

[30]

Michael R. Fellows and Bart M. P. Jansen. FPT is Characterized by Useful Obstruction Sets: Connecting Algorithms, Kernels, and Quasi-Orders. Accepted to ACM Transactions on Computation Theory. 33 pages. 2013. arXiv: 1305.3102.

[31]

Bart M. P. Jansen. On Sparsification for Computing Treewidth. Submitted upon invitation to the IPEC 2013 Special Issue of Algorithmica. 29 pages. 2013. arXiv: 1308.3665.

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

Awards

  • The paper "Vertex Cover Kernelization Revisited" was selected by ACM Computing Reviews as a notable article in computing in 2013.
  • The paper "On Sparsification for Computing Treewidth" was awarded an Excellent Student Paper Award at IPEC 2013.