Michael Dom Friedrich-Schiller-Universität Jena Fakultät für Mathematik und Informatik Institut für Informatik Lehrstuhl Theoretische Informatik I Ernst-Abbe-Platz 2 Room: 3323 D-07743 Jena Fed. Rep. of Germany Phone: +49-3641-9-46324 Fax: +49-3641-9-46322 E-mail:

Publications

• Michael Dom, Michael R. Fellows, and Frances A. Rosamond.
  Parameterized Complexity of Stabbing Rectangles and Squares in the Plane.
  Original publication © Springer, published in:
  Proceedings of the 3rd International Workshop on Algorithms and Computation (WALCOM '09),
  LNCS. Springer, 2009. To appear.
  
  
• Michael Dom and Somnath Sikdar.
  The Parameterized Complexity of the Rectangle Stabbing Problem and its Variants.
  Original publication © Springer, published in:
  Proceedings of the 2nd International Frontiers of Algorithmics Workshop (FAW '08),
  volume 5059 of LNCS, pages 288–299. Springer, 2008.
  
  
• Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger.
  Capacitated Domination and Covering: A Parameterized Perspective.
  Original publication © Springer, published in:
  Proceedings of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC '08),
  volume 5018 of LNCS, pages 78–90. Springer, 2008.
  
  
• Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.
  Closest 4-Leaf Power is Fixed-Parameter Tractable.
  Original publication © Elsevier B. V., published in:
  Discrete Applied Mathematics, 156(18):3345–3361. Elsevier B. V, 2008.
  
  
• Michael Dom.
  Set Cover with Almost Consecutive Ones.
  Original publication © Springer, published in:
  Encyclopedia of Algorithms, pages 832–834. Springer, 2008.
  
  
• Michael Dom, Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke.
  Red-Blue Covering Problems and the Consecutive Ones Property.
  Original publication © Elsevier B. V., published in:
  Journal of Discrete Algorithms, 6(3):393–407. Elsevier B. V, 2008.
  
  
• Michael Dom, Falk Hüffner, and Rolf Niedermeier.
  Tiefensuche (Ariadne und Co.).
  Original publication © Springer, published in:
  Taschenbuch der Algorithmen,
  eXamen.press, pages 61–73. Springer, 2008.
  In German language. Originally appeared as part of the Algorithmus der Woche series.
  
  
• Michael Dom.
  Compact Routing.
  Original publication © Springer, published in:
  Algorithms for Sensor and Ad Hoc Networks,
  volume 4621 of LNCS, pages 187–202. Springer, 2007.
  
  
• Michael Dom and Rolf Niedermeier.
  The Search for Consecutive Ones Submatrices: Faster and More General.
  Original publication in:
  Proceedings of the 3rd Algorithms and Complexity in Durham (ACiD '07) Workshop,
  volume 9 of Texts in Algorithmics, pages 43–54. College Publications, 2007.
  
  
• Michael Dom, Jiong Guo, and Rolf Niedermeier.
  Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems.
  Original publication © Springer, published in:
  Proceedings of the 4th Annual Conference on Theory and Applications of Models of Computation (TAMC '07),
  volume 4484 of LNCS, pages 680–691. Springer, 2007.
  
  
• Harald Sack, Uwe Krüger, and Michael Dom.
  A Knowledge Base on NP-complete Decision Problems and its Application in Bibliographic Search.
  Original publication in:
  XML-Tage 2006, Berlin, September 2006.
  
  
• Michael Dom, Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke.
  Minimum Membership Set Covering and the Consecutive Ones Property.
  Original publication © Springer, published in:
  Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT '06),
  volume 4059 of LNCS, pages 339–350. Springer, 2006.
  Journal version appeared in Journal of Discrete Algorithms (see above).
  
  
• Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truß.
  Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments.
  Original publication © Springer, published in:
  Proceedings of the 6th International Conference on Algorithms and Complexity (CIAC '06),
  volume 3998 of LNCS, pages 320–331. Springer, 2006.
  
  
• Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.
  Error Compensation in Leaf Power Problems.
  Original publication © Springer, published in:
  Algorithmica, 44(4):363–381. Springer, 2006.
  
  
• Michael Dom, Jiong Guo, and Rolf Niedermeier.
  Bounded Degree Closest k-Tree Power is NP-complete.
  Original publication © Springer, published in:
  Proceedings of the 11th International Computing and Combinatorics Conference (COCOON '05),
  volume 3595 of LNCS, pages 757–766. Springer, 2005.
  
  
• Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.
  Extending the Tractability Border for Closest Leaf Powers.
  Original publication © Springer, published in:
  Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG '05),
  volume 3787 of LNCS, pages 397–408. Springer, 2005.
  Journal version appeared in Discrete Applied Mathematics (see above).
  
  
• Michael Dom, Jiong Guo, Falk Hüffner, and Rolf Niedermeier.
  Error Compensation in Leaf Root Problems.
  Original publication © Springer, published in:
  Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC '04),
  volume 3341 of LNCS, pages 389–401. Springer, 2004.
  Journal version appeared in Algorithmica (see above).

Talks

• 2nd International Frontiers of Algorithmics Workshop (FAW '08), June 19–21, 2008, Changsha, China:
  The Parameterized Complexity of the Rectangle Stabbing Problem and its Variants
  (with additional slides from the "Oberseminar Theoretische Informatik", February 04, 2008, Friedrich-Schiller-Universität Jena)
  
  
• "Oberseminar Theoretische Informatik", June 09, 2008, Friedrich-Schiller-Universität Jena:
  Capacitated Domination and Covering
  
  
• Seminar, October 19, 2007, Institute of Mathematical Sciences, Chennai, India:
  Approximation and Fixed-Parameter Algorithms for Consecutive Ones Submatrix Problems
  
  
• 3rd Algorithms and Complexity in Durham (ACiD '07) Workshop, September 17–19, 2007, Durham, England:
  The Search for Consecutive Ones Submatrices: Faster and More General
  
  
• GI-Dagstuhl Seminar "Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs" (Dagstuhl Event Nº 07281), July 08–13, 2007, Schloß Dagstuhl, Germany:
  Fixed-Parameter Algorithms for Consecutive Ones Submatrix Problems
  
  
• 10th Scandinavian Workshop on Algorithm Theory (SWAT '06), July 06–08, 2006, Riga, Latvia:
  Minimum Membership Set Covering and the Consecutive Ones Property
  
  
• 6th International Conference on Algorithms and Complexity (CIAC '06), May 29–31, 2006, Rome, Italy:
  Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments
  
  
• GI-Dagstuhl Research Seminar "Algorithms for Sensor and Ad Hoc Networks" (Dagstuhl Event Nº 05473), November 23–25, 2005, Schloß Dagstuhl, Germany:
  Compact Routing
  
  
• 11th International Computing and Combinatorics Conference (COCOON '05), August 16–19, 2005, Kunming, China:
  Bounded Degree Closest k-Tree Power is NP-complete
  
  
• 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG '05), June 23–25, 2005, Metz, France:
  Extending the Tractability Border for Closest Leaf Powers
  
  
• 51. Workshop über Datenstrukturen, Effiziente Algorithmen und Komplexitätstheorie (Theorietag 2005), March 15, 2005, Erlangen, Germany:
  Bounded Degree Closest k-Tree Power is NP-complete

Theses

• Michael Dom.
  Fehler-Korrektur bei Leaf-Root-Problemen ("Error Correction in Leaf Root Problems").
  Diploma thesis, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, October 2004. In German language.

Teaching

• Übungen zu "Algorithmik", WS 2008/09
  
  
• Seminar "Combinatorial Pattern Matching", WS 2008/09
  
  
• Proseminar "Graphalgorithmen", WS 2008/09
  
  
• Proseminar "Graphentheorie und ihre Anwendungen", SS 2008
  
  
• Übungen zu "Algorithmik", WS 2007/08
  
  
• Übungen zu "Komplexitätstheorie", SS 2007
  
  
• Übungen zu "Algorithmik", WS 2006/07
  
  
• Proseminar "Graphentheorie und ihre Anwendungen", WS 2006/07
  
  
• Übungen zu "Diskrete Mathematik und Logik 2 (DML 2)", SS 2006
  
  
• Übungen zu "Diskrete Mathematik und Logik 1 (DML 1)", WS 2005/06
  
  
• Übungen zu "Parametrisierte Algorithmen", WS 2005/06
  
  
• Übungen zu "Berechenbarkeit und Komplexität", SS 2005
  
  
• Übungen zu "Algorithmen für harte Probleme", WS 2004/05

Experimental FTP Problem Database

• Welcome page of our NP and Parametrized Problem Ontology

Miscellaneous

• Tips for Latex and Bibtex (in German language)
  
  
• Link to my private homepage (in German language)

Old stuff

• Practical course "Client/Server Systems", Universität Tübingen, WS 1999/2000:
  Documentation and exercise about CORBA (in German language)

Last modified: Mar 26, 2008