Dr. rer. nat. René van Bevern (Рене ван Беверн)
- 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.
- Sometimes I am lucky and happen to take some good photo with my cell phone camera. The photos are available at 500px.com.
- The Complexity of Arc Routing Problems. In Ángel Corberán and Gilbert Laporte (eds.) Arc Routing: Problems, Methods, and Applications, SIAM, 2014.
Invited Journal Articles
- Myhill-Nerode Methods for Hypergraphs. Algorithmica (ISAAC'13 special issue), in press, 2015.
- Towards Optimal and Expressive Kernelization for d-Hitting Set. Algorithmica (COCOON'12 special issue), 2014.
- A New View on Rural Postman Based on Eulerian Extension and Matching. Journal of Discrete Algorithms (IWOCA'11 special issue), 2012.
- Exploiting hidden structure in selecting features to distinguish vectors. Journal of Computer and System Sciences
- Approximability and parameterized complexity of multicover by c-intervals. Information Processing Letters, 2015.
- On the Parameterized Complexity of Computing Balanced Partitions in Graphs. Theory of Computing Systems, 2015.
- Network-Based Vertex Dissolution. SIAM Journal on Discrete Mathematics, 2015.
- Interval Scheduling and Colorful Independent Sets. Journal of Scheduling, in press, 2014.
- Constant-factor approximations for Capacitated Arc Routing without triangle inequality. Operations Research Letters, 2014.
- Approximation and Tidying—A Problem Kernel for s-Plex Cluster Vertex Deletion. Algorithmica, 2012.
- Parameterized Algorithmics for Finding Connected Motifs in Biological Networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011.
- Approximation algorithms for mixed, windy, and capacitated arc routing problems. Best paper at ATMOS'15, Patras, Greece.
- H-Index Manipulation by Merging Articles: Models, Theory, and Experiments. IJCAI'15, Buenos Aires, Argentina.
- Network-Based Dissolution. MFCS'14, Budapest, Hungary. A journal version appeared in SIAM Journal on Discrete Mathematics.
- Star Partitions of Perfect Graphs.
- Myhill-Nerode Methods for Hypergraphs. At ISAAC'13, Hong Kong, China. A journal version appeared in the ISAAC'13 special issue of Algorithmica.
- On the parameterized complexity of graph bisections. At WG'13, Lübeck, Germany. A journal version appeared in Theory of Computing Systems.
- A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems. At MFCS'13, Klosterneuburg, Austria. Journal version with many new results under review.
- Parameterized Complexity of DAG Partitioning. At CIAC'13, Barcelona, Spain. Improved algorithms and experimental evaluations can be found in my Dissertation. .
- Interval Scheduling and Colorful Independent Sets. At ISAAC'12, Teipei, Taiwan. A journal version appeared in Journal of Scheduling. .
- Towards Optimal and Expressive Kernelization for d-Hitting Set. At COCOON'12, Sydney, Australia. A journal version appeared in the COCOON'12 special issue of Algorithmica. .
- Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs. At IPEC'11, Saarbrücken, Germany.
- A New View on Rural Postman Based on Eulerian Extension and Matching. At IWOCA'11, Victoria, Canada. A journal version appeared in the IWOCA'11 special issue of Journal of Discrete Algorithms.
- From Few Components to an Eulerian Graph by Adding Arcs. At WG'11, Teplá Monastery, Czech Republic.
- Measuring Indifference: Unit Interval Vertex Deletion. At WG'10, Zarós, Greece.
- Kernelization through Tidying—A case study based on s-Plex Cluster Vertex Deletion. At LATIN'10, Oaxaca, Mexico. A journal version appeared in Algorithmica.
- 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.
- 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.
- 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.
Manuscripts under review
- Above-Guarantee Parameterization of Edge Modification Problems. September 2015.
- Well-Formed Separator Sequences, with an Application to Hypergraph Drawing. September 2015.
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack. August 2015.
- Partitioning Perfect Graphs into Stars. May 2015.
- Fixed-parameter algorithms for DAG Partitioning. November 2014.
Thanks to Christoph Taszus for providing me with web space. © 2010–2015 René van Bevern. Last modified 2015-07-17.