Research

Research Interests

I am interested in theoretical and practical issues of computer science. More precisely in the design, analysis and efficient implementation of exact and approximate algorithms and data structures concerning:

• Graph Algorithms
• Cycle Bases and Algebraic Graph Theory
• Matchings with Preferences

I am also interested in experimental algorithmics and programming languages.

Program Committees

• ICTCS'07, 10th Italian Conference on Theoretical Computer Science.

Thesis

• Minimum Cycle Basis, Algorithms and Applications. [pdf]
  PhD thesis, Universität des Saarlandes, 2006.

Manuscripts, technical reports and submitted papers

• with Kurt Mehlhorn.
  Minimum Cycle Bases: Faster and Simpler
  submitted to journal [pdf]

Journal Publications

• with T. Kavitha, K. Mehlhorn, and K. Paluch.
  An O(m²nlogn) Algorithm for Minimum Cycle Basis of Graphs
  Algorithmica. In Press [web]
• Reducing Rank-Maximal to Maximum Weight Matching
  Theoretical Computer Science. In Press [web]
• with C. Gotsman, K. Kaligosi, K. Mehlhorn, and E. Pyrga.
  Cycle Bases of Graphs and Sampled Manifolds.
  Computer Aided Geometric Design, 24(8-9):464-480, 2007.
  Special issue: Discrete Differential Geometry [pdf, web]
• with T. Kavitha, K. Mehlhorn, and K. Paluch.
  Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents problem. [pdf, web]
  ACM Transactions on Algorithms, 3(2), 2007.
• with K. Mehlhorn.
  Implementing Minimum Cycle Basis Algorithms. [ps.gz, pdf, web]
  ACM Journal of Experimental Algorithmics, 11(2):1-14, 2006.
• with R. Irving, T. Kavitha, K. Mehlhorn, and K. Paluch.
  Rank-maximal Matchings. [ps.gz, pdf, web]
  ACM Transactions on Algorithms, 2(4):602-610, 2006.

Conference Publications (refereed)

• with C-C. Huang, T. Kavitha, and M. Nasre.
  Bounded Unpopularity Matchings [pdf]
  In Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT'08).
  to appear
• with T. Kavitha, and K. Mehlhorn.
  New Approximation Algorithms for Minimum Cycle Bases of Graphs. [ps.gz, pdf, web]
  In Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS'07).
• with K. Mehlhorn.
  Implementing Minimum Cycle Basis Algorithms. [ps.gz, pdf, web]
  In Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA'05).
• with T. Kavitha, K. Mehlhorn, and K. Paluch.
  A Faster Algorithm for Minimum Cycle Basis of Graphs. [ps.gz, pdf, web]
  In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04).
• with T. Kavitha, K. Mehlhorn, and K. Paluch.
  Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents problem. [ps.gz, pdf, web]
  In Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS'2004).
• with R. Irving, T. Kavitha, K. Mehlhorn, and K. Paluch.
  Rank-maximal Matchings. [ps.gz, pdf, web]
  In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04).

Research Software

• Rank-Maximal Matchings.
  This is a LEDA extension package which implements efficient algorithms which compute rank-maximal matchings in bipartite graphs.
• Minimum Cycle Basis.
  This is a LEDA extension package which implements exact and approximation algorithms in order to compute a minimum cycle basis of edge-weighted undirected and directed graphs.