Publications

Textbooks

• H.-J. Böckenhauer, J. Hromkovič:
  Formale Sprachen - Endliche Automaten, Grammatiken, lexikalische und syntaktische Analyse.
  Springer Vieweg, 2013.
• H.-J. Böckenhauer, D. Bongartz:
  Algorithmic Aspects of Bioinformatics.
  Springer, 2007.
• H.-J. Böckenhauer, D. Bongartz:
  Algorithmische Grundlagen der Bioinformatik.
  Teubner, 2003.

Book Chapter

• H.-J. Böckenhauer, J. Hromkovič, S. Seibert:
  Stability of approximation.
  In: T. F. Gonzalez (ed.): Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC, 2007, Chapter 31.

Publications in Refereed Journals

• H.-J. Böckenhauer, T. Mömke, M. Steinová:
  Improved approximations for TSP with simple precedence constraints.
  Journal of Discrete Algorithms, to appear.
• H.-J. Böckenhauer, K. Freiermuth, J. Hromkovič, T. Mömke, A. Sprock, B. Steffen:
  Steiner tree reoptimization in graphs with sharpened triangle inequality.
  Journal of Discrete Algorithms 11, 2012, pp. 73-86.
• D. Bilò, H.-J. Böckenhauer, D. Komm, R. Královič, T. Mömke, S. Seibert, A. Zych:
  Reoptimization of the shortest common superstring problem.
  Algorithmica 61(2), 2011, pp. 227-251.
• H.-J. Böckenhauer, J. Hromkovič, A. Sprock:
  On the hardness of reoptimization with multiple given solutions.
  Fundamenta Informaticae 110, 2011, pp. 59-76.
• H.-J. Böckenhauer, M. Forišek, J. Oravec, B. Steffen, K. Steinhöfel, M. Steinová:
  The uniform minimum-ones 2SAT problem and its application to haplotype classification.
  RAIRO Theoretical Informatics and Applications 44, 2010, pp. 363-377.
• H.-J. Böckenhauer, D. Komm:
  Reoptimization of the metric deadline TSP.
  Journal of Discrete Algorithms 8, 2010, pp. 87-100.
• H.-J. Böckenhauer, J. Hromkovič, R. Královič, T. Mömke, P. Rossmanith:
  Reoptimization of Steiner trees: changing the terminal set.
  Theoretical Computer Science 410, 2009, pp. 3428-3435.
• H.-J. Böckenhauer, J. Kneis, J. Kupke:
  Approximation hardness of deadline-TSP reoptimization.
  Theoretical Computer Science 410, 2009, pp. 2241-2249.
• H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, W. Unger:
  On k-connectivity problems with sharpened triangle inequality.
  Journal of Discrete Algorithms 6, 2008, pp. 605-617.
• H.-J. Böckenhauer, J. Hromkovič, J. Kneis, J. Kupke:
  The parameterized approximability of TSP with deadlines.
  Theory of Computing Systems 41(3), 2007, pp. 431-444.
• H.-J. Böckenhauer, D. Bongartz:
  A weighted HP model for protein folding with diagonal contacts.
  RAIRO Theoretical Informatics and Applications 41, 2007, pp. 375-402.
• H.-J. Böckenhauer, L. Forlizzi, J. Hromkovič, J. Kneis, J. Kupke, G. Proietti, P. Widmayer:
  On the approximability of TSP on local modifications of optimally solved instances.
  Algorithmic Operations Research 2(2), 2007, pp.83-93.
• H.-J. Böckenhauer, D. Bongartz:
  Protein folding in the HP model on grid lattices with diagonals.
  Discrete Applied Mathematics 155(2), 2007, pp. 230-256.
• H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, W. Unger:
  On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality.
  Theoretical Computer Science 326(1-3), 2004, pp. 137-153.
• H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger:
  Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
  Theoretical Computer Science 285(1), 2002, pp. 3-24.
• H.-J. Böckenhauer, S. Seibert:
  Improved lower bounds on the approximability of the traveling salesman problem.
  RAIRO Theoretical Informatics and Applications 34, 2000, pp. 213-255.
• H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger:
  Approximation algorithms for the TSP with sharpened triangle inequality.
  Information Processing Letters 75, 2000, pp. 133-138.
• H.-J. Böckenhauer:
  Communication in the two-way listen-in vertex-disjoint paths mode.
  Theoretical Computer Science 264 (1), 2001, pp. 65-90.
• H.-J. Böckenhauer:
  Two open problems in communication in edge-disjoint paths modes.
  Acta Mathematica et Informatica Universitatis Ostraviensis 7, 1999, pp. 109-117.

Publications in Refereed Books and Proceedings

• H.-J. Böckenhauer, L. Keller:
  On the approximability of splitting-SAT in 2-CNF Horn formulas.
  Proc. of the 24th International Workshop on Combinatorial Algorithms (IWOCA 2013), to appear.
• H.-J. Böckenhauer, J. Hromkovič, D. Komm, S. Krug, J. Smula, A. Sprock:
  The string guessing problem as a method to prove lower bounds on the advice complexity.
  Proc. of the 19th Annual International Computing and Combinatorics Conference (COCOON 2013), to appear.
• M. P. Bianchi, H.-J. Böckenhauer, J. Hromkovič, S. Krug, B. Steffen:
  On the advice complexity of the online L(2,1)-coloring problem on paths and cycles.
  Proc. of the 19th Annual International Computing and Combinatorics Conference (COCOON 2013), to appear.
• H.-J. Böckenhauer, M. Steinová:
  Improved approximations for ordered TSP on near-metric graphs.
  Proc. of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013), LNCS 7741, Springer 2013, pp. 157-168.
• M. P. Bianchi, H.-J. Böckenhauer, J. Hromkovič, L. Keller:
  Online coloring of bipartite graphs with and without advice.
  Proc. of the 18th Annual International Conference on Computing and Combinatorics (COCOON 2012), LNCS 7434, Springer 2012, pp. 519-530.
• H.-J. Böckenhauer, D. Komm, R. Královič, P. Rossmanith:
  On the advice complexity of the knapsack problem.
  Proc. of the 10th Latin American Symposium on Theoretical Informatics (LATIN 2012), LNCS 7256, Springer 2012, pp. 61-72.
• H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič:
  On the advice complexity of the k-server problem.
  Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Part I, LNCS 6755, Springer 2011, pp. 207-218.
• H.-J. Böckenhauer, K. Freiermuth, J. Hromkovič, T. Mömke, A. Sprock, B. Steffen:
  The Steiner tree reoptimization problem with sharpened triangle inequality.
  Proc. of the 7th International Conference on Algorithms and Complexity (CIAC 2010), LNCS 6078, Springer 2010, pp. 180-191.
• H.-J. Böckenhauer, R. Klasing, T. Mömke, M. Steinová:
  Improved approximations for TSP with simple precedence constraints.
  Proc. of the 7th International Conference on Algorithms and Complexity (CIAC 2010), LNCS 6078, Springer 2010, pp. 61-72.
• H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič, T. Mömke:
  On the advice complexity of online problems.
  Proc. of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), LNCS 5878, Springer 2009, pp. 331-340.
• D. Bilò, H.-J. Böckenhauer, D. Komm, R. Královič, T. Mömke, S. Seibert, A. Zych:
  Reoptimization of the shortest common superstring problem.
  Proc. of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), LNCS 5577, Springer 2009, pp. 78-91.
• H.-J. Böckenhauer, A. Dayem Ullah, L. Kapsokalivas, K. Steinhöfel:
  A local move set for protein folding in triangular lattice models.
  Proc. of the 8th Workshop on Algorithms in Bioinformatics (WABI 2008), LNCS 5251, Springer 2008, pp. 369-381.
• H.-J. Böckenhauer, D. Komm:
  Reoptimization of the metric deadline TSP.
  Proc. of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), LNCS 5162, Springer 2008, pp. 156-167.
• D. Bilò, H.-J. Böckenhauer, J. Hromkovič, R. Královič, T. Mömke, P. Widmayer, A. Zych:
  Reoptimization of Steiner Trees.
  Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), LNCS 5124, Springer 2008, pp. 258-269.
• H.-J. Böckenhauer, J. Hromkovič, R. Královič, T. Mömke, K. Steinhöfel:
  Efficient algorithms for the spoonerism problem.
  Proc. of the 4th International Conference on Fun with Algorithms (FUN 2007), LNCS 4475, Springer 2007, pp. 78-92.
• H.-J. Böckenhauer, L. Forlizzi, J. Hromkovič, J. Kneis, J. Kupke, G. Proietti, P. Widmayer:
  Reusing optimal TSP solutions for locally modified input instances (extended abstract).
  Proc. of the 4th IFIP International Conference on Theoretical Computer Science (IFIP TCS 2006), Springer 2006, pp. 251-270.
• H.-J. Böckenhauer, J. Hromkovič, J. Kneis, J. Kupke:
  On the approximation hardness of some generalizations of TSP (extended abstract).
  Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), LNCS 4059, Springer 2006, pp. 184-195.
• H.-J. Böckenhauer, D. Bongartz:
  Protein folding in the HP model on grid lattices with diagonals (extended abstract).
  Proc. of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), LNCS 3153, Springer 2004, pp. 227-238.
• H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, W. Unger:
  On k-edge-connectivity problems with sharpened triangle inequality.
  Proc. of the 5th Italian Conference on Algorithms and Complexity (CIAC 2003), LNCS 2653, Springer Verlag 2003, pp. 189-200.
• H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, W. Unger:
  On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality.
  Proc. of the 22nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2002), LNCS 2556, Springer Verlag 2002, pp. 59-70.
• H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger:
  Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem (extended abstract).
  Proc. of the 4th Italian Conference on Algorithms and Complexity (CIAC 2000), LNCS 1767, Springer Verlag 2000, pp. 72-86.
• H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger:
  An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (extended abstract).
  Proc. of the 17th Symposium on Theoretical Aspects of Computer Science (STACS 2000), LNCS 1770, Springer Verlag 2000, pp. 382-394.
• H.-J. Böckenhauer:
  Communication in the two-way listen-in vertex-disjoint paths mode (extended abstract).
  Proc. of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 1998), LNCS 1517, Springer Verlag 1998, pp. 38-49.
• H.-J. Böckenhauer:
  Two open problems in communication in edge-disjoint paths modes.
  Proc. of the MFCS'98 Workshop on Communication, RWTH Aachen Press, pp. 10-17.

Invited Contributions in Books and Proceedings

• H.-J. Böckenhauer, J. Hromkovič, D. Komm, R. Královič, P. Rossmanith:
  On the power of randomness versus advice in online computation.
  In: H. Bordihn, M. Kutrib, B. Truthe (eds.): Languages Alive - Essays Dedicated to Jürgen Dassow on the Occasion of His 65th Birthday, LNCS 7300, Springer Verlag 2012, pp. 30-43.
• H.-J. Böckenhauer, J. Hromkovič, A. Sprock:
  Knowing all optimal solutions does not help for TSP reoptimization.
  In: J. Kelemen, A. Kelemenová (eds.): Computation, Cooperation and Life - Essays Dedicated to Gheorghe Păun on the Occasion of His 60th Birthday, LNCS 6610, Springer Verlag 2011, pp. 7-15.
• H.-J. Böckenhauer, J. Hromkovič, T. Mömke:
  Improved approximations for hard optimization problems via problem instance classification.
  In: C. S. Calude, G. Rozenberg, A. Salomaa (eds.): Rainbow of Computer Science - Essays Dedicated to Hermann Maurer on the Occasion of His 70th Birthday, LNCS 6570, Springer Verlag 2011, pp. 3-19.
• H.-J. Böckenhauer, J. Hromkovič, T. Mömke, P. Widmayer:
  On the hardness of reoptimization.
  Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008), LNCS 4910, Springer Verlag 2008, pp. 50-65.
• H.-J. Böckenhauer, J. Hromkovič:
  Stability of approximation algorithms or parameterization of the approximation ratio.
  Proc. of the 9th International Symposium on Operations Research in Slovenia (SOR’07), Slovenian Society Informatika - Section for Operational Research 2007, pp. 23-28.

Technical Reports

• H.-J. Böckenhauer, J. Hromkovič, D. Komm, S. Krug, J. Smula, A. Sprock:
  The string guessing problem as a method to prove lower bounds on the advice complexity.
  Electronic Colloquium on Computational Complexity (ECCC), TR12-162, 2012.
• H.-J. Böckenhauer, D. Komm, R. Královič, P. Rossmanith:
  On the advice complexity of the knapsack problem.
  Technical Report 740, ETH Zurich, 2011.
• H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič:
  On the advice complexity of the k-server problem.
  Technical Report 703, ETH Zurich, 2010.
• H.-J. Böckenhauer, J. Oravec, B. Steffen, K. Steinhöfel, M. Steinová:
  The uniform minimum-ones 2SAT problem and its application to haplotype classification.
  Technical Report 673, ETH Zurich, 2010.
• H.-J. Böckenhauer, K. Freiermuth, J. Hromkovič, T. Mömke, A. Sprock, B. Steffen:
  The Steiner tree reoptimization problem with sharpened triangle inequality.
  Technical Report 658, ETH Zurich, 2010.
• H.-J. Böckenhauer, R. Klasing, T. Mömke, M. Steinová:
  Improved approximations for TSP with simple precedence constraints.
  Technical Report 650, ETH Zurich, 2009.
• H.-J. Böckenhauer, D. Komm, R. Královič, R. Královič, T. Mömke:
  Online algorithms with advice.
  Technical Report 614, ETH Zurich, 2009.
• H.-J. Böckenhauer, D. Bongartz, J. Hromkovič, R. Klasing, G. Proietti, S. Seibert, W. Unger:
  On k-connectivity problems with sharpened triangle inequality.
  Technical Report RR-1430-07, LaBRI, 2007.
• H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger:
  Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
  Electronic Colloquium on Computational Complexity (ECCC), 6(31), 1999.

Doctoral Thesis

• H.-J. Böckenhauer:
  On the Inapproximability of the Metric Traveling Salesman Problem.
  Lehrstuhl für Informatik I, RWTH Aachen, Aachen 2000.