Homepage
Danny Hermelin
Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 323
66123 Saarbrücken
Germany
Email:
Get my email address via email
Phone: +49 681 9325 1023
Fax: +49 681 9325 1099
- Graph Algorithms
- Parameterized Complexity
- Approximation Algorithms
- Combinatorial Pattern Matching
Journal Articles:
- D. Hermelin, C.-C. Huang, S. Kratsch, M. Wahlström:
Parameterized Two-Player Nash Equilibrium.
Algorithmica, accepted.
- D. Hermelin, G.M. Landau, S. Landau, O. Weimann:
Unified Compression-Based Acceleration of Edit-Distance Computation.
Algorithmica, accepted.
- M.R. Fellows, D. Hermelin, F.A. Rosamond:
Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs and their Algorithmic Applications.
Algorithmica, accepted.
- M.R. Fellows, T. Hartman, D. Hermelin, G.M. Landau, F.A. Rosamond, L. Rozenberg:
Haplotype Inference Constrained by Plausible Haplotype Data.
IEEE/ACM Trans. Comput. Biology Bioinform. 8(6): 1692-1699 (2011).
- R. Bar-Yehuda, D. Hermelin, D. Rawitz:
Minimum vertex cover in rectangle graphs.
Computational Geometry 44(6-7): 356-364 (2011).
- M.R. Fellows, G. Fertin, D. Hermelin, S. Vialette:
Upper and lower bounds for finding connected motifs in vertex-colored graphs.
J. Comput. Syst. Sci. 77(4): 799-811 (2011).
- O. Ben-Zwi, D. Hermelin, D. Lokshtanov, I. Newman:
Treewidth governs the complexity of target set selection.
Discrete Optimization 8(1): 87-96 (2011).
- D. Hermelin, D. Rawitz:
Optimization problems in multiple subtree graphs.
Discrete Applied Mathematics 159(7): 588-594 (2011).
- A. Butman, D. Hermelin, M. Lewenstein, D. Rawitz:
Optimization problems in multiple-interval graphs.
ACM Transactions on Algorithms 6(2): (2010).
- R. Bar-Yehuda, D. Hermelin, D. Rawitz:
An Extension of the Nemhauser-Trotter Theorem to Generalized Vertex Cover with Applications.
SIAM J. Discrete Math. 24(1): 287-300 (2010).
- G. Fertin, D. Hermelin, R. Rizzi, S. Vialette:
Finding common structured patterns in linear graphs.
Theor. Comput. Sci. 411(26-28): 2475-2486 (2010).
- M.R. Fellows, D. Hermelin, J. Flum, M. Muller, F.A. Rosamond:
W-Hierarchies Defined by Symmetric Gates.
Theory Comput. Syst. 46(2): 311-339 (2010).
- H.L. Bodlaender, R.G. Downey, M.R. Fellows, D. Hermelin:
On problems without polynomial kernels.
J. Comput. Syst. Sci. 75(8): 423-434 (2009).
- M.R. Fellows, D. Hermelin, F.A. Rosamond, S. Vialette:
On the parameterized complexity of multiple-interval graph problems.
Theor. Comput. Sci. 410(1): 53-61 (2009).
- D. Hermelin, D. Rawitz, R. Rizzi, S. Vialette:
The Minimum Substring Cover problem.
Inf. Comput. 206(11): 1303-1312 (2008).
- G. Blin, G. Fertin, D. Hermelin, S. Vialette:
Fixed-parameter algorithms for protein similarity search under mRNA structure constraints.
J. Discrete Algorithms 6(4): 618-626 (2008).
- M. Crochemore, D. Hermelin, G.M. Landau, D. Rawitz, S. Vialette:
Approximating the 2-interval pattern problem.
Theor. Comput. Sci. 395(2-3): 283-297 (2008).
- G. Blin, E. Blais, D. Hermelin, P. Guillon, M. Blanchette, N. El-Mabrouk:
Gene Maps Linearization Using Genomic Rearrangement Distances.
Journal of Computational Biology 14(4): 394-407 (2007).
- R. Backofen, S. Chen, D. Hermelin, G.M. Landau, M.A. Roytberg, O. Weimann, K. Zhang:
Locality and Gaps in RNA Comparison.
Journal of Computational Biology 14(8): 1074-1087 (2007).
Articles in Proceedings of Refereed Conferences:
- D. Hermelin and X. Wu.
Weak Compositions and Their Applications to Polynomial Lower Bounds for Kernelization.
SODA 2011, to appear.
- D. Hermelin, C.-C. Huang, S. Kratsch, M. Wahlström:
Parameterized Two-Player Nash Equilibrium.
WG 2011, 215-226.
- M.R. Fellows, T. Friedrich, D. Hermelin, N. Narodytska, F.A. Rosamond:
Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable.
IJCAI 2011, 522-527.
- D. Hermelin, M. Mnich, E.J. Van Leeuwen and G.J. Woeginger.
Domination when the Stars Are Out.
ICALP 2011: 462-473.
- D. Hermelin, A. Levy, O. Weimann, and R. Yuster:
Distance Oracles for Vertex-Labeled Graphs.
ICALP 2011: 490-501.
- R. Bar-Yehuda, D. Hermelin, D. Rawitz:
Minimum Vertex Cover in Rectangle Graphs.
ESA 2010: 255-266.
- I. Nor, D. Hermelin, S. Charlat, J. Engelstadter, M. Reuter, O. Duron, M.-F. Sagot:
Mod/Resc Parsimony Inference.
CPM 2010: 202-213.
- Z. Gotthilf, D. Hermelin, G.M. Landau, M. Lewenstein:
Restricted LCS.
SPIRE 2010: 250-257.
- O. Ben-Zwi, D. Hermelin, D. Lokshtanov, I. Newman:
An exact almost optimal algorithm for target set selection in social networks.
ACM Conference on Electronic Commerce 2009: 355-362.
- M.R. Fellows, T. Hartman, D. Hermelin, G.M. Landau, F.A. Rosamond, L. Rozenberg:
Haplotype Inference Constrained by Plausible Haplotype Data.
CPM 2009: 339-352.
- M.R. Fellows, D. Hermelin, F.A. Rosamond:
Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs.
IWPEC 2009: 149-160.
- D. Hermelin, G.M. Landau, S. Landau, O. Weimann:
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression.
STACS 2009: 529-540.
- R. Bar-Yehuda, D. Hermelin, D. Rawitz:
An Extension of the Nemhauser-Trotter Theorem to Generalized Vertex Cover with Applications.
WAOA 2009: 13-24.
- D. Hermelin, D. Rawitz:
Optimization Problems in Multiple Subtree Graphs.
WAOA 2009: 194-204.
- Z. Gotthilf, D. Hermelin, M. Lewenstein:
Constrained LCS: Hardness and Approximation.
CPM 2008: 255-262.
- H.L. Bodlaender, R.G. Downey, M.R. Fellows, D. Hermelin:
On problems without polynomial kernels.
ICALP 2008: 563-574.
- M.R. Fellows, D. Hermelin, M. Muller, F.A. Rosamond:
A Purely Democratic Characterization of W[1].
IWPEC 2008: 103-114.
- G. Fertin, D. Hermelin, R. Rizzi, S. Vialette:
Common Structured Patterns in Linear Graphs: Approximation and Combinatorics.
CPM 2007: 241-252.
- M.R. Fellows, G. Fertin, D. Hermelin, S. Vialette:
Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs.
ICALP 2007: 340-351.
- A. Butman, D. Hermelin, M. Lewenstein, D. Rawitz:
Optimization problems in multiple-interval graphs.
SODA 2007: 268-277.
- D. Hermelin, D. Rawitz, R. Rizzi, S. Vialette:
The Minimum Substring Cover problem.
WAOA 2007: 170-183.
- R. Backofen, D. Hermelin, G.M. Landau, O. Weimann:
Local Alignment of RNA Sequences with Arbitrary Scoring Schemes.
CPM 2006: 246-257.
- M. Crochemore, D. Hermelin, G.M. Landau, S. Vialette:
Approximating the 2-interval pattern problem.
ESA 2005: 426-437.
- R. Backofen, D. Hermelin, G.M. Landau, O. Weimann:
Normalized Similarity of RNA Sequences.
SPIRE 2005: 360-369.
- G. Blin, G. Fertin, D. Hermelin, S. Vialette:
Fixed-parameter algorithms for protein similarity search under mRNA structure constraints.
WG 2005: 271-282.
