Michael Dom Former member of the Friedrich-Schiller-Universität Jena Fakultät für Mathematik und Informatik Institut für Informatik Lehrstuhl Theoretische Informatik I 07743 Jena Fed. Rep. of Germany E-mail: see my private homepage I have left the group "Theoretische Informatik I" of Rolf Niedermeier in November 2009 and will not read my e-mail regularly.

Publications

BibTeX bibliography data of the publications
DBLP publication list

• Michael Dom, Daniel Lokshtanov, and Saket Saurabh.
  Kernelization Lower Bounds Through Colors and IDs.
  Original publication © ACM, published in:
  ACM Transactions on Algorithms, 11(2):Article No. 13. ACM, 2014.
• Michael Dom, Michael R. Fellows, Frances A. Rosamond, and Somnath Sikdar.
  The Parameterized Complexity of Stabbing Rectangles.
  Original publication © Springer, published in:
  Algorithmica, 62(1–2):564–594. Springer, 2012.
• André Nichterlein, Michael Dom, and Rolf Niedermeier.
  Aspects of a Multivariate Complexity Analysis for Rectangle Tiling.
  Original publication © Elsevier B. V., published in:
  Operation Research Letters, 39(5):346–351. Elsevier B. V., 2011.
• Michael Dom, Falk Hüffner, and Rolf Niedermeier.
  Depth-First Search (Ariadne & Co.)
  Original publication © Springer, published in:
  Algorithms Unplugged, pages 57–68. Springer, 2011.
  German version appeared in Taschenbuch der Algorithmen (see below).
• Michael Dom, Jiong Guo, and Rolf Niedermeier.
  Approximation and Fixed-Parameter Algorithms for Consecutive Ones Submatrix Problems.
  Original publication © Elsevier B. V., published in:
  Journal of Computer and System Sciences, 76(3–4):204–221. Elsevier B. V., 2010.
  (For slides, see below.)
• Michael Dom.
  Algorithmic Aspects of the Consecutive-Ones Property.
  Original publication © EATCS, published in:
  Bulletin of the European Association for Theoretical Computer Science, 98:27–59. EATCS, 2009.
• Michael Dom, Daniel Lokshtanov, and Saket Saurabh.
  Incompressibility through Colors and IDs.
  Original publication © Springer, published in:
  Proceedings of the 36th International Colloquium on Automata, Languages, and Programming (ICALP '09), volume 5555 of LNCS, pages 378–389. Springer, 2009.
  Journal version appeared in ACM Transactions on Algorithms (see above).
  (For slides, see below.)
• Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truss.
  Fixed-Parameter Tractability Results for Feedback Set Problems in Tournaments.
  Original publication © Elsevier B. V., published in:
  Journal of Discrete Algorithms, 8(1):76–86. Elsevier B. V., 2010.
  (For slides, see below.)
• 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), volume 5431 of LNCS, pages 298–309. Springer, 2009.
  Journal version appeared in Algorithmica (see above).
  (For slides, see below.)
• 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.
  Journal version appeared in Algorithmica (see above).
  (For slides, see below.)
• 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.
  (For slides, see below.)
• 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.
  (For slides, see below.)
• 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. English version appeared in Algorithms Unplugged (see above). 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.
  (For slides, see below.)
• 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.
  Journal version appeared in Journal of Computer and System Sciences (see above).
  (For slides, see below.)
• 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.
  Journal version appeared in Journal of Computer and System Sciences (see above).
  (For slides, see below.)
• 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.
  Journal version appeared in Journal of Discrete Algorithms (see above).
  (For slides, see below.)
• 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.
  (For slides, see below.)
• 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.
  (For slides, see below.)
• 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).
  (For slides, see below.)
• 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).
  (For slides, see below.)

Talks / Slides

• 36th International Colloquium on Automata, Languages, and Programming (ICALP '09), July 05–12, 2009, Rhodes, Greece:
  Incompressibility through Colors and IDs
• 3rd Annual Workshop on Algorithms and Computation (WALCOM '09), February 18–20, 2009, Kolkata, India:
  Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• 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
• "Oberseminar Theoretische Informatik", 2004, Friedrich-Schiller-Universität Jena:
  Error Compensation in Leaf Root Problems

Theses

• Recognition, Generation, and Application of Binary Matrices with the Consecutive-Ones Property.
  Dissertation, Institut für Informatik, Friedrich-Schiller-Universität Jena, 2008. Original version published by Cuvillier, 2009.
• 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, 2004. In German language.

Teaching

(in German language)

Material

• Übersicht über die Komplexitätsklassen aus der Vorlesung und den Übungen "Komplexitätstheorie"

Veranstaltungen

• Übungen zu "Komplexitätstheorie", SS 2009
• Proseminar "Kryptologie", SS 2009
• Ü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 FPT 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: 2015 © Michael Dom, all rights reserved.