Lehr- und Forschungsgebiet Theoretische Informatik

Joachim Kneis

E-mail:kneis@cs.rwth-aachen.de
Postal address:Joachim Kneis
Lehrgebiet Theoretische Informatik
RWTH Aachen
Ahornstraße 55
52056 Aachen
Federal Republic of Germany
Phone:+49-241-80-21132
Room:6114 (Building E2)

Publications:

  • J. Kneis, A. Langer, and P. Rossmanith
    A Fine-grained Analysis of a Simple Independent Set Algorithm
    In Proceedings of the 29th Foundations of Software Technology and Theoretical Computer Science Conference (FSTTCS)
    to appear, 2009.
  • D. Raible, H. Fernau, J. Kneis, D. Kratsch, A. Langer, P. Rossmanith and M. Liedloff
    An exact algorithm for the Maximum Leaf Spanning Tree problem
    In Proceedings of the 4th International Workshop on Exact and Parameterized Computation (IWPEC)
    to appear, 2009.
  • R. Ganian, P. Hlineny, J. Kneis, A. Langer, J. Obdržálek and P. Rossmanith
    On Digraph Width Measures in Parameterized Algorithmics
    In Proceedings of the 4th International Workshop on Exact and Parameterized Computation (IWPEC))
    to appear, 2009.
  • J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S.-H. Sze, and F. Zhang
    Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
    In SIAM Journal on Computing
    accepted for publication, 2009.
  • H.-J. Böckenhauer, J. Kneis, and J. Kupke
    Approximation hardness of deadline-TSP reoptimization
    In Theoretical Computer Science
    410, pages 21-32, 2009.
  • J. Kneis, D. Mölle, S. Richter, and P. Rossmanith.
    A bound on the pathwidth of sparse graphs with applications to exact algorithms
    In SIAM Journal on Discrete Mathematics
    23 (1), pages 407-427, 2009.
  • J. Kneis and A. Langer
    A Practical Approach to Courcelle's Theorem
    In Proceedings of the 4th Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS)
    pages 99-106,2008.
  • J. Kneis, A. Langer, and P. Rossmanith
    A new algorithm for finding trees with many leaves
    In {Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC)
    LNCS 5369, pages 270-281, 2008.
  • J. Kneis, A. Langer, and P. Rossmanith
    Improved upper bounds for partial vertex cover
    In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
    LNCS 5344, pages 240-251, 2008.
  • J. Kneis, D. Mölle, and P. Rossmanith
    Partial vs. complete domination: t-dominating set
    In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM)
    LNCS 4362, pages 367-376, 2007.
  • H.-J. Böckenhauer, J. Hromkovic, J. Kneis, J. Kupke
    The Parameterized Approximability of TSP with Deadlines
    In Theory of Computing Systems
    41 (3), pages 431-444. 2007.
  • J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
    Parameterized power domination complexity
    In Information Processing Letters
    98 (4), pages 145-149, 2006.
  • J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
    Divide-and-color
    In Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
    LNCS 4271, pages 58-67, 2006.
  • J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
    Intuitive algorithms and t-vertex cover
    In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC)
    LNCS 4288, pages 598-607, 2006.
  • H.-J. Böckenhauer, J. Hromkovic, J. Kneis, J. Kupke
    On the approximation hardness of some generalizations of TSP
    In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT)
    LNCS 4059, pages 184-195, 2006.
  • H.-J. Böckenhauer, L. Forlizzi, J. Hromkovic, J. Kneis, J. Kupke, G. Proietti, and P. Widmayer
    Reusing optimal TSP solutions for locally modified input instances
    In Proceedings of the 19th IFIP World Computer Congress
    IFIP, volume 209, pages 251-270, 2006.
  • J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
    Algorithms based on the treewidth of sparse graphs
    In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
    LNCS 3787, pages 385-396, 2005.
  • J. Kneis, D. Mölle, S. Richter, and P. Rossmanith
    On the parameterized complexity of exact satisfiability problems
    In Proceedings of the 30th Conference on Mathematical Foundations of Computer Science (MFCS)
    LNCS 3618, pages 568-579, 2005.
  • J. Gerlach and J. Kneis
    Generic programming for scientific computing in C++, Java, and C#
    In Proceedings of the 5th International Workshop on Advanced Parallel Programming Technologies
    LNCS 2834, pages 301-310, 2003.