Parametrisierte Algorithmik

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 65062910

• Final Report Year: 2010

Final Report Abstract

No abstract available

Publications

• Fixed-parameter algorithms for cluster vertex deletion. In Proc. 8th LATIN, Band 4598 von LNCS, pp. 711–722. Springer, 2008
  F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier
  
• Fixedparameter algorithms for Kemeny scores. In Proc. 4th AAIM, Band 5034 von LNCS, pp. 60–71, Springer, 2008
  N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier und F. A. Rosamond
  
• Parameterized algorithms and hardness results for some graph motif problems. In Proc. 19th CPM, Band 5029 von LNCS, pp. 31–43. Springer, 2008
  N. Betzler, M. R. Fellows, C. Komusiewicz und R. Niedermeier
  
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems. In Proc. 34th MFCS, Band 5734 von LNCS, pp. 319–330, Springer, 2009
  M. R. Fellows, J. Guo, H. Moser und R. Niedermeier
  
• A generalization of Nemhauser and Trotter’s local optimization theorem. In Proc. 26th STACS, Leibniz International Proceedings in Informatics (LIPIcs), pp. 409–420, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2009
  M. R. Fellows, J. Guo, H. Moser und R. Niedermeier
  
• A more relaxed model for graph-based data clustering: s-plex editing. In Proc. 5th AAIM, Band 5564 von LNCS, pp. 226–239, Springer, 2009
  J. Guo, C. Komusiewicz, R. Niedermeier und J. Uhlmann
  
• Fixedparameter algorithms for Kemeny rankings. Theoretical Computer Science, 410(52): 5384–5397, 2009
  N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier und F. A. Rosamond
  
• Graphbased data clustering with overlaps. In Proc. 15th COCOON, Band 5609 von LNCS, pp. 516–526, Springer, 2009
  M. R. Fellows, J. Guo, C. Komusiewicz, R. Niedermeier und J. Uhlmann
  
• How similarity helps to efficiently compute Kemeny rankings. In Proc. 8th AAMAS, pp. 657–664, 2009
  N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier und F. A. Rosamond
  
• Iterative compression for exactly solving NP-hard minimization problems. In: Algorithmics of Large and Complex Networks, volume 5515 in Lecture Notes in Computer Science, pp. 65–80, Springer, 2009
  J. Guo, H. Moser und R. Niedermeier
  
• Average parameterization and partial kernelization for computing medians In Proc. 9th LATIN, Band 6034 von LNCS, pp. 60–71, Springer, 2010
  N. Betzler, J. Guo, C. Komusiewicz und R. Niedermeier
  
• Average parameterization and partial kernelization for computing medians. Journal of Computer and System Sciences, 2010
  N. Betzler, J. Guo, C. Komusiewicz und R. Niedermeier
  
• Extended islands of tractability for parsimony haplotyping. In Proc. 21st CPM, erscheint in LNCS, Springer, 2010
  R. Fleischer, J. Guo, R. Niedermeier, J. Uhlmann, Y. Wang, M. Weller und W. Xi
  
• Fixed-parameter algorithms for cluster vertex deletion. Theory of Computing Systems, 47(1): 196–217, 2010
  F. Hüffner, C. Komusiewicz, H. Moser und R. Niedermeier
  
• Incremental list coloring of graphs, parameterized by conservation In Proc. 7th TAMC, Band 6108 von LNCS, pp. 258-270, Springer, 2010
  S. Hartung und R. Niedermeier
  
• Parameterized computational complexity of Dodgson and Young elections. Information and Computation, 208(2): 165–177, 2010
  N. Betzler, J. Guo und R. Niedermeier
  
• Reflections on multivariate algorithmics and problem parameterization. In Proc. 27th STACS, Volume 5 in Leibniz International Proceedings in Informatics (LIPIcs), pp. 17-32, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2010
  R. Niedermeier