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

Dr. rer. nat. René van Bevern (Рене ван Беверн)

Postdoc at Novosibirsk State University, Novosibirsk, Russian Federation. E-Mail: rvb@nsu.ru

Work

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.

From January 2011 till May 2015
PhD student and postdoc at the Algorithms and Complexity Theory group, TU Berlin, Germany, funded by the DFG project “Data Driven Parameterized Algorithmics for Graph Modification Problems”.
From April till December 2010
PhD student at the Chair Theoretische Informatik I, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany, funded by the DFG project “Algorithms for Generating Quasi-Regular Structures in Graphs”.

Publications

Also see Google Scholar, DBLP, arXiv, Scopus, and ResearchGate.

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, SIAM, 2014. [chapter, book]

Invited Journal Articles

  1. René van Bevern, Rodney G. Downey, Michael R. Fellows, Serge Gaspers, Frances Rosamond: Myhill-Nerode Methods for Hypergraphs. Algorithmica (ISAAC'13 special issue), in press, 2015. [paper, 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, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, Gerhard J. Woeginger: Approximability and parameterized complexity of multicover by c-intervals. Information Processing Letters, 2015. [paper, abstract, preprint]
  2. 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, 2015. [paper, abstract, preprint].
  3. René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Network-Based Vertex Dissolution. SIAM Journal on Discrete Mathematics, 2015. [paper, abstract, preprint]
  4. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller: Interval Scheduling and Colorful Independent Sets. Journal of Scheduling, in press, 2014. [paper, abstract, preprint].
  5. 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]
  6. 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].
  7. 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, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge, Toby Walsh: H-Index Manipulation by Merging Articles: Models, Theory, and Experiments. Accepted for IJCAI'15. [preprint]
  2. René van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Network-Based Dissolution. MFCS'14, Budapest, Hungary. [paper, abstract, preprint]. A journal version appeared in SIAM Journal on Discrete Mathematics.
  3. 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.
  4. 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 appeared in the ISAAC'13 special issue of Algorithmica.
  5. 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.
  6. 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.
  7. 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 is under review. Improved algorithms and experimental evaluations can be found in my Dissertation.
  8. René van Bevern, Mathias Mnich, Rolf Niedermeier, and Mathias Weller: Interval Scheduling and Colorful Independent Sets. At ISAAC'12, Teipei, Taiwan, December 2012. [paper, abstract]. A journal version appeared in Journal of Scheduling.
  9. 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.
  10. 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]
  11. 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.
  12. 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]
  13. 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]
  14. 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. [abstract, thesis, read online, 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, Christian Komusiewicz, Manuel Sorge: Approximation algorithms for mixed, windy, and capacitated arc routing problems, June 2015. [abstract, manuscript]
  2. René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, Manuel Sorge: Well-Formed Separator Sequences with an Application to Hypergraph Drawing, April 2015.
  3. René van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger: Partitioning Perfect Graphs into Stars, March 2015
  4. René van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý: Fixed-parameter algorithms for DAG Partitioning, November 2014.
  5. Vincent Froese, René van Bevern, Rolf Niedermeier, Manuel Sorge: Exploiting hidden structure in selecting features to distinguish vectors, July 2014


Thanks to Christoph Taszus for providing me with web space.

© 2010–2015 René van Bevern. Last modified 2015-05-28.