Picture of the Colosseum in Rome

Essentials

Browse my publications and curriculum vitae.

My main research interests are:

  • networks and algorithms for networks,
  • parameterized complexity,
  • approximation algorithms,
  • computational geometry, and
  • complexity theory.

Recently

(last updated: February 2013)

 

Contact

E-mail:
erikjan@mpi-inf.mpg.de
E.J.van.Leeuwen@dis.uniroma1.it
Mail address:
Max-Planck Institut für Informatik
Campus E1 4
66123 Saarbrücken
Germany
Visiting address:
Room 323
Campus E1 4
66123 Saarbrücken
Germany

Publications

A list of my publications can be found below. Some of them can also be found through DBLP.

Journal papers

Accepted

  • T: Integer Representations of Convex Polygon Intersection Graphs
    A: Müller, T.M., van Leeuwen, E.J., van Leeuwen, J.
    P: SIAM Journal on Discrete Mathematics
    to appear
  • T: Structure of Polynomial-Time Approximation
    A: van Leeuwen, E.J., van Leeuwen, J.
    P: Theory of Computing Systems 50:4 (2012), pp. 641-674.
  • T: Parameterized Complexity of the Spanning Tree Congestion Problem
    A: Bodlaender, H.L., Fomin, F.V., Golovach, P.A., Otachi, Y., van Leeuwen, E.J.
    P: Algorithmica 64:1 (2012), pp. 85-111.
  • T: Weisfeiler-Lehman Graph Kernels
    A: Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.
    P: Journal of Machine Learning Research 12 (September 2011), pp. 2539-2561
  • T: Spanners of Bounded Degree Graphs
    A: Fomin, F.V., Golovach, P.A., van Leeuwen, E.J.
    P: Information Processing Letters 111:3 (January 2011), pp. 142-144
  • T: Bij Benadering Optimaliseren
    A: van Leeuwen, E.J.
    P: Nieuw Archief voor de Wiskunde 11:1 (March 2010), pp. 57-60
    Not available online

Submitted

  • T: Parameterized Complexity of Firefighting
    A: Bazgan, C., Chopin, M., Cygan, M., Fellows, M.R., Fomin, F.V., van Leeuwen, E.J.
  • T: Fast Dynamic Programming on Graph Decompositions
    A: van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P., van Leeuwen, E.J., Vatshelle, M.

Conference papers

Accepted

  • T: Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
    A: Pilipczuk, M., Pilipczuk, M., Sankowski, P., van Leeuwen, E.J.
    P: STACS 2013
  • T: Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
    A: Hermelin, D., Mnich, M., van Leeuwen, E.J.
    P: ESA 2012
  • T: Induced Disjoint Paths in Claw-Free Graphs
    A: Golovach, P.A., Paulusma, D., van Leeuwen, E.J.
    P: ESA 2012
  • T: On the Complexity of Metric Dimension
    A: Diaz, J., Pottonen, O.M., Serna, M., van Leeuwen, E.J.
    P: ESA 2012
  • T: Reducing a Target Interval to a Few Exact Queries
    A: Nederlof, J., van Leeuwen, E.J., van der Zwaan, R.
    P: MFCS 2012
  • T: Induced Disjoint Paths in AT-free Graphs
    A: Golovach, P.A., Paulusma, D., van Leeuwen, E.J.
    P: SWAT 2012 in Fomin, F.V., Kaski, P. (eds.) Algorithm Theory - SWAT 2012, 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012, Proceedings, Lecture Notes in Computer Science, Volume 7357, Springer-Verlag, Berlin, 2012, pp. 153--164.
  • T: Making Life Easier for Firefighters
    A: Fomin, F.V., Heggernes, P., van Leeuwen, E.J.
    P: FUN 2012 in Kranakis, E., Krizanc, D., Luccio, F. (eds.) Fun with Algorithms, 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012, Proceedings, Lecture Notes in Computer Science, Volume 7288, Springer-Verlag, Berlin, 2012, pp. 177--188.
  • T: k-Gap Interval Graphs
    A: Fomin, F.V., Gaspers, S., Golovach, P., Suchan, K., Szeider, S., van Leeuwen, E.J., Vatshelle, M., Villanger, Y.
    P: LATIN 2012 in Fernández-Baca, D. (ed.) LATIN 2012: Theoretical Informatics, 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012, Proceedings, Lecture Notes in Computer Science, Volume 7256, Springer-Verlag, Berlin, 2012, pp. 350--361.
  • T: Parameterized Complexity of Firefighting Revisited
    A: Cygan, M., Fomin, F.V., van Leeuwen, E.J.
    P: IPEC 2011 in Marx, D., Rossmanith, P. (eds.) Parameterized and Exact Computation, 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 2011, Revised Selected Papers, Lecture Notes in Computer Science, Volume 7112, Springer-Verlag, Berlin, 2012, pp. 13--26.
  • T: Domination When the Stars Are Out
    A: Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.
    P: ICALP 2011 in Aceto, L., Henziger, M., Sgall, J. (eds.) Automata, Languages and Programming, 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I, Lecture Notes in Computer Science, Volume 6755, Springer-Verlag, Berlin, 2011, pp. 462--473.
  • T: Integer Representations of Convex Polygon Intersection Graphs
    A: Müller, T.M., van Leeuwen, E.J., van Leeuwen, J.
    P: SoCG 2011 Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SCG '11), ACM, New York, 2011, pp.~300--307.
  • T: Convex Polygon Intersection Graphs
    A: van Leeuwen, E.J., van Leeuwen, J.
    P: GD 2010 in Brandes, U., Cornelsen, S. (eds.) Graph Drawing, 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010. Revised Selected Papers., Lecture Notes in Computer Science, Volume 6502, Springer-Verlag, Berlin, 2011, pp. 377-388.
  • T: PTAS for Weighted Set Cover on Unit Squares
    A: Erlebach, T., van Leeuwen, E.J.
    P: APPROX-RANDOM 2010 in Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 13th International Workshop, APPROX 2010 and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010, Proceedings, Lecture Notes in Computer Science, Volume 6302, Springer-Verlag, Berlin, 2010, pp. 166-177.
  • T: Faster Algorithms on Clique and Branch Decompositions
    A: Bodlaender, H.L., van Leeuwen, E.J., van Rooij, J.M.M., Vatshelle, M.
    P: MFCS 2010 in Hlineny, P., Kucera, A. (eds.) Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010, Proceedings, Lecture Notes in Computer Science, Volume 6281, Springer-Verlag, Berlin, 2010, pp. 174-185.
  • T: Complexity Results for the Spanning Tree Congestion Problem
    A: Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J.
    P: WG 2010 in Thilikos, D.M. (ed.) Graph-Theoretic Concepts in Computer Science, 36th International Workshop, WG 2010, Zarós, Greece, June 28-30, 2010, Revised Papers, Lecture Notes in Computer Science, Volume 6410, Springer-Verlag, Berlin, 2010, pp. 3-14
  • T: Domination in Geometric Intersection Graphs
    A: Erlebach, T., van Leeuwen, E.J.
    P: LATIN 2008 in Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L.(eds.) Theoretical Informatics - LATIN 2008, 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008, Proceedings, Lecture Notes in Computer Science, Volume 4957, Springer-Verlag, Berlin, 2008, pp. 747-758
  • T: Approximating Geometric Coverage Problems
    A: Erlebach, T., van Leeuwen, E.J.
    P: SODA 2008 in Teng, S.-H. SODA '08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008, pp. 1267-1276
  • T: Better Approximation Schemes for Disk Graphs
    A: van Leeuwen, E.J.
    P: SWAT 2006 in Arge, L., Freivalds, R. (eds.) Algorithm Theory - SWAT 2006, 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedings, Lecture Notes in Computer Science, Volume 4059, Springer-Verlag, Berlin, 2006, pp. 316-327
  • T: Approximation Algorithms for Unit Disk Graphs
    A: van Leeuwen, E.J.
    P: WG 2005 in Kratsch, D. (ed.) Graph-Theoretic Concepts in Computer Science, 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Selected Papers, Lecture Notes in Computer Science, Volume 3787, Springer-Verlag, Berlin, 2005, pp. 351-361

PhD thesis, Technical reports, and More

PhD thesis

  • T: Optimization and Approximation on Systems of Geometric Objects
    A: van Leeuwen, E.J.
    P: PhD Thesis, University of Amsterdam, 2009
    N: Defended June 16, 2009. Research carried out at Centrum Wiskunde & Informatica.

arXiv

  • T: Reducing a Target Interval to a Few Exact Queries
    A: Nederlof, J., van Leeuwen, E.J., van der Zwaan, R.
    P: arXiv:1208:4225 [cs.DS], 2012
  • T: Parameterized Complexity of Induced H-Matching on Claw-Free Graphs
    A: Hermelin, D., Mnich, M., van Leeuwen, E.J.
    P: arXiv:1206.7105 [cs.DM], 2012
  • T: On the Complexity of Metric Dimension
    A: Diaz, J., Pottonen, O.M., Serna, M., van Leeuwen, E.J.
    P: arXiv:1107.2256 [cs.CC], 2012
  • T: Induced Disjoint Paths in Claw-Free Graphs
    A: Golovach, P.A., Paulusma, D., van Leeuwen, E.J.
    P: arXiv:1202.4419 [cs.DM], 2012
  • T: k-Gap Interval Graphs
    A: Fomin, F.V., Gaspers, S., Golovach, P., Suchan, K., Szeider, S., van Leeuwen, E.J., Vatshelle, M., Villanger, Y.
    P: arXiv:1112.3244 [cs.DS], 2011
  • T: Parameterized Complexity of Firefighting Revisited
    A: Cygan, M., Fomin, F.V., van Leeuwen, E.J.
    P: arXiv:1109.4729 [cs.DM], 2011
  • T: Planar Metric Dimension is NP-complete
    A: Diaz, J., Pottonen, O.M., van Leeuwen, E.J.
    P: arXiv:1107.2256v1 [cs.CC], 2011
  • T: Domination When the Stars Are Out
    A: Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.
    P: arXiv:1012.0012 [cs.DS], 2010

Technical reports

  • T: Convex Polygon Intersection Graphs
    A: van Leeuwen, E.J., van Leeuwen, J.
    P: Technical Report UU-CS-2010-026, Department of Information and Computing Sciences, Utrecht University, 2010
  • T: Complexity Results for the Spanning Tree Congestion Problem,
    A: Otachi, Y., Bodlaender, H.L., van Leeuwen, E.J.,
    P: Technical Report UU-CS-2010-007, Department of Information and Computing Sciences, Utrecht University, 2010
  • T: Structure of Polynomial-Time Approximation
    A: van Leeuwen, E.J., van Leeuwen, J.
    P: Technical Report UU-CS-2009-034, Department of Information and Computing Sciences, Utrecht University, 2009
  • T: On the Representation of Disk Graphs
    A: van Leeuwen, E.J., van Leeuwen, J.
    P: Technical Report UU-CS-2006-037, Department of Information and Computing Sciences, Utrecht University, 2006
  • T: Approximation Algorithms for Unit Disk Graphs
    A: van Leeuwen, E.J.
    P: Technical Report UU-CS-2004-066, Department of Information and Computing Sciences, Utrecht University, 2004

Abstracts

  • T: Domination When the Stars Are Out
    A: Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.
    P: in DIMAP Workshop on Combinatorics and Graph Theory, 2011
    Not available online
  • T: Structure of Polynomial-Time Approximation
    A: van Leeuwen, E.J.
    P: in Dagstuhl Seminar 09511: Parameterized Complexity and Approximation Algorithms, 2009, p. 14
  • T: Approximating Geometric Coverage Problems
    A: Erlebach, T., van Leeuwen, E.J.
    P: in International Symposium on Combinatorial Optimization 2008, 2008, pp. 36-37
  • T: Better Approximation Schemes for Disk Graphs
    A: van Leeuwen, E.J.
    P: in Dagstuhl Seminar 07151: Geometry in Sensor Networks, 2007, p. 11

Posters

  • T: Algorithms for Wireless Networks
    A: van Leeuwen, E.J.
    P: BRICKS project poster

Show all publications

Curriculum vitae

Positions

  • since 2013 PostDoc at Max-Planck Institut für Informatik, Saarbrücken, Germany
  • 2012 - 2013 PostDoc at Sapienza University of Rome, Italy (with Stefano Leonardi)
  • 2010 - 2012 PostDoc at University of Bergen, Norway (with Fedor Fomin)
  • 2009 - 2010 PostDoc at Eindhoven University of Technology, The Netherlands (with Gerhard Woeginger)
  • 2005 - 2009 PhD student at Centrum Wiskunde & Informatica, The Netherlands (with Lex Schrijver)
  • 2004 Guest researcher at Utrecht University, The Netherlands (with Hans Bodlaender)

Degrees

  • 2009 PhD degree from University of Amsterdam
  • 2004 Master's degree with highest honors (cum laude) from Utrecht University
  • 2000 Propaedeutic degree with highest honors (cum laude) from Utrecht University

Program committees

Prizes

  • 2008 Winner Philips Mathematics Prize for PhD Students
  • 2007 Winner BRICKS 2007 Dissemination award

Teaching

  • 2012 Instructor on Theoretical Computer Science course, Sapienza University of Rome. See for example my slides on Circulations, stable matching, and primal-dual.
  • 2011 Taught Mini-Course Approximation Algorithms, University of Bergen.
  • 2006 - 2007 Assisted on the Advanced Algorithms course (Fall 2007), the Ontwerp van Algoritmen 3 (Algorithm Design 3) course (Spring 2007), and the Advanced Algorithms course (Winter 2006/2007) at TU Eindhoven.
  • 2001 - 2003 Assisted on several courses at Utrecht University.