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

René van Bevern

Dr. rer. nat. René van Bevern, researcher 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, 2014. [abstract]

Invited Journal Articles

  1. René van Bevern, Michael R. Fellows, Serge Gaspers, Frances Rosamond: Myhill-Nerode Methods for Hypergraphs. Algorithmica, accepted for publication, 2014. [abstract, preprint]
  2. René van Bevern: Towards Optimal and Expressive Kernelization for d-Hitting Set. Algorithmica (COCOON'12 special issue), 2014. [paper, abstract, preprint, source code].
  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 (IWOCA'11 special issue), 2012. [paper, abstract, preprint].

Journal Articles

  1. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller: Interval Scheduling and Colorful Independent Sets. Journal of Scheduling, accepted for publication, 2014. [abstract, preprint].
  2. René van Bevern, Sepp Hartung, André Nichterlein, Manuel Sorge: Constant-factor approximations for Capacitated Arc Routing without triangle inequality. Operations Research Letters, 2014. [paper, abstract, preprint]
  3. 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, in press, 2014. [paper, abstract, preprint].
  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.
  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, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Graph-Based Dissolution. To appear at MFCS'14, Budapest, Hungary. [abstract, preprint]. A journal version is under review.
  2. René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Star Partitions of Perfect Graphs. At ICALP'14, Copenhagen, Denmark. [paper, abstract, preprint]. A journal version is under review.
  3. 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]
  4. René van Bevern, Andreas Emil Feldmann, Manuel Sorge, Ondřej Suchý: On the parameterized complexity of graph bisections. At WG'13, Lübeck, Germany, June 2013. [paper, abstract , preprint, slides]. A journal version appeared in Theory of Computing Systems.
  5. 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]. Journal version with many new results under review.
  6. 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]. A journal version with improved algorithms and experimental evaluations is under review.
  7. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller: Interval Scheduling and Colorful Independent Sets. At ISAAC'12, Teipei, Taiwan, December 2012. A journal version is accepted for publication at Journal of Scheduling. [paper, abstract].
  8. René van Bevern: Towards Optimal and Expressive Kernelization for d-Hitting Set. At COCOON'12, Sydney, Australia, August 2012. [paper, abstract, slides]. A journal version appeared in the COCOON'12 special issue of Algorithmica.
  9. 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]
  10. Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller: A New View on Rural Postman Based on Eulerian Extension and Matching. At IWOCA'11, Victoria, Canada, June 2011. A journal version appeared in the IWOCA'11 special issue of Journal of Discrete Algorithms.
  11. 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]
  12. 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]
  13. René van Bevern, Hannes Moser, and Rolf Niedermeier: Kernelization through Tidying—A case study based on s-Plex Cluster Vertex Deletion. At LATIN'10, Oaxaca, Mexico, April 2010. [paper, abstract, slides]. A journal version appeared in Algorithmica.

Theses

  1. René van Bevern: Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications. Dissertation, Institut für Softwaretechnik und Theoretische Informatik, Technische Universität Berlin, Germany, June 2014. In press. [manuscript, slides]
  2. 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]
  3. 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, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger: Approximability and parameterized complexity of multicover by c-intervals, July 2014.
  2. René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Partitioning Perfect Graphs into Stars, July 2014
  3. René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Graph-Based Vertex Dissolution, July 2014.
  4. Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge: Exploiting hidden structure in selecting features to distinguish vectors, July 2014
  5. René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý: Fixed-parameter algorithms for DAG Partitioning, March 2014.


Thanks to Christoph Taszus for providing me with web space.

© 2010–2014 René van Bevern. Last modified 2014-09-15.