Lehr- und Forschungsgebiet Theoretische Informatik


Dr. Joachim Kneis

E-mail:kneis@cs.rwth-aachen.de
Postal address:Dr. 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 New Algorithm for Finding Trees with Many Leaves
    Accepted for Algorithmica.
  • L. Brankovic, H. Fernau, J. Kneis, D. Kratsch, A. Langer, M. Liedloff, D. Raible and P. Rossmanith
    Breaking the 2^n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles
    In Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC)
    LNCS 6078, pages 311-322. Springer, 2010
  • 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)
    LIPIcs 4, pages 287-298. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 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)
    LNCS 5917, pages 161-172. Springer, 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))
    LNCS 5917, pages 185-197. Springer, 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
    38 (6), pages 2526-2547, 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.