Lake Baikal, Siberia in January.
Озеро Байкал в январе.

René van Bevern

Dipl.-Inf. René van Bevern, researcher and PhD student at Technische Universität Berlin, Germany. [arXiv, DBLP, Google Scholar, Scopus]

Technische Universität Berlin
Algorithmik und Komplexitästheorie
Sekretariat TEL 5-1
Ernst-Reuter-Platz 7
10587 Berlin

Room: TEL 509
Office Phone: (+49) 30 314 24166
E-Mail: rene.vanbevern@tu-berlin.de

My work focuses on developing fast algorithms for NP-hard discrete optimization problems by exploiting structures in practically occuring data (``fixed-parameter algorithms''). Ideally, the algorithms run in linear time when certain parameters in the input data are bounded by constants.

My work is funded by the project “Data Driven Parameterized Algorithmics for Graph Modification Problems” of Deutsche Forschungsemeinschaft (DFG), earlier by the project “Algorithms for Generating Quasi-Regular Structures in Graphs”.

Prior to my work in Berlin, I have been working at Friedrich-Schiller-Universität Jena, Thuringia, Germany.

Book Chapters

  1. René van Bevern, Rolf Niedermeier, Manuel Sorge, Mathias Weller: The Complexity of Arc Routing Problems. In Ángel Corberán and Gilbert Laporte (eds.) Arc Routing: Problems, Methods, and Applications, in press, SIAM, 2013. [abstract]

Journal Articles

  1. René van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý: On the Parameterized Complexity of Computing Balanced Partitions in Graphs. Theory of Computing Systems, accepted for publication 2014. [abstract, preprint]

    A preliminary version appeared at WG'13, Lübeck, Germany, June 2013. [paper, abstract, slides]
  2. René van Bevern: Towards Optimal and Expressive Kernelization for d-Hitting Set. Algorithmica (invited to COCOON'12 special issue), 2013. [paper, abstract, preprint, slides, source code].

    A preliminary version appeared at COCOON'12, Sydney, Australia, August 2012.
  3. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller: A New View on Rural Postman Based on Eulerian Extension and Matching. Journal of Discrete Algorithms (invited to IWOCA'11 special issue), 2012. [paper, abstract, preprint].

    A preliminary version appeared at IWOCA'11, Victoria, Canada, June 2011.
  4. René van Bevern, Hannes Moser, and Rolf Niedermeier: Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion. Algorithmica, 2012. [paper, abstract, preprint, slides].

    A preliminary version appeared at LATIN'10, Oaxaca, México, April 2010.
  5. Nadja Betzler, René van Bevern, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier: Parameterized Algorithmics for Finding Connected Motifs in Biological Networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011. [paper, abstract, preprint, source code]

Conference Articles

  1. René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Star Partitions of Perfect Graphs. To appear at ICALP'14. [abstract, preprint]
  2. René van Bevern, Michael R. Fellows, Serge Gaspers, Frances Rosamond: Myhill-Nerode Methods for Hypergraphs. At ISAAC'13, Hong Kong, December 2013. [paper, abstract, preprint]

    A journal version with a more algorithmical point of view is currently under review. [abstract, preprint]
  3. Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge: A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems. At MFCS'13, Klosterneuburg, Austria, August 2013. [paper, abstract, preprint]
  4. René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý: Parameterized Complexity of DAG Partitioning. At CIAC'13, Barcelona, Spain, May 2013. [paper, abstract, preprint]
  5. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller: Interval Scheduling and Colorful Independent Sets. At ISAAC'12, Taipei, Taiwan, December 2012. [paper, abstract, preprint]

    A journal version answering many left-open questions and adding experimental evaluation is under review. [abstract, preprint]
  6. René van Bevern, Sepp Hartung, Frank Kammer, Rolf Niedermeier, and Mathias Weller: Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs. At IPEC'11, Saarbrücken, Germany, September 2011. [paper, abstract, preprint, slides]
  7. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller: From Few Components to an Eulerian Graph by Adding Arcs. At WG'11, Teplá Monastery, Czech Republic, June 2011. [paper, abstract, preprint]
  8. René van Bevern, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier: Measuring Indifference: Unit Interval Vertex Deletion. At WG'10, Zarós, Greece, June 2010. [paper, abstract, preprint, slides]

Theses

  1. René van Bevern: The Computational Hardness and Tractability of Restricted Seriation Problems on Inaccurate Data. Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, April 2010. [thesis, slides]
  2. René van Bevern: Graph-based data clustering: a quadratic-vertex problem kernel for s-Plex Cluster Vertex Deletion. Studienarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, September 2009. [abstract, thesis, slides]

Manuscripts under review

  1. René van Bevern, Sepp Hartung, André Nichterlein, Manuel Sorge: Constant-factor approximations for Capacitated Arc Routing without triangle inequality. [abstract, preprint]
  2. René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Graph-Based Dissolution. [abstract, preprint]
  3. René van Bevern, Michael R. Fellows, Serge Gaspers, Frances Rosamond: Myhill-Nerode Methods for Hypergraphs. [abstract, preprint]
  4. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller: Interval Scheduling and Colorful Independent Sets. [abstract, preprint]


Thanks to Christoph Taszus for providing me with web space.

© 2010–2013 René van Bevern. Last modified 2013-12-22.