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
07743 Jena
Fed. Rep. of Germany

Phone: +49-3641-9-46324
Fax: +49-3641-9-46322
E-mail:

Publications

BibTeX bibliography data of the publications
DBLP publication list

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. Elsevier B. V. To appear.
(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. EATCS. To appear.
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. Springer, 2009. To appear.
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.
(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.
(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 to appear. 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 to appear 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 to appear 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.
(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. 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.