Publications of Martin Kutz

Journal Papers

Martin Kutz, Khaled M. Elbassioni, Irit Katriel and Meena Mahajan:
Simultaneous matchings: Hardness and approximation.
Journal of Computer and System Sciences, 74(5):884-897, 2008.
Manuel Bodirsky and Martin Kutz:
Determining the Consistency of Partial Tree Descriptions.
Accepted for publication in Artificial Intelligence.
[ps] [pdf] (preliminary version)
Martin Kutz:
Conway's Angel in Three Dimensions.
Theoretical Computer Science, 349(3):443-451, 2005.
[ps] [pdf]
Martin Kutz:
The Complexity of Boolean Matrix Root Computation.
Theoretical Computer Science, 325(3):373-390, 2004.
Dennis Epple and Martin Kutz:
Parity Lights.
The Mathematical Gazette, 88(511):46-56, 2004.
[ps] [pdf] © The Mathematical Gazette
Martin Kutz:
Lower Bounds for Lucas Chains.
SIAM Journal on Computing, 31(6):1896-1908, 2002.
[ps] [pdf] © SIAM

Conference Papers

Daniel Dumitriu, Stefan Funke, Martin Kutz and Nikola Milosavljevic:
On the Locality of Extracting a 2-Manifold in R3.
In Proceedings of SWAT 2008, Gothenburg, Sweden, 2008.
Daniel Dumitriu, Stefan Funke, Martin Kutz and Nikola Milosavljevic:
How much Geometry it takes to Reconstruct a 2-Manifold in R3.
In Proceedings of ALENEX 2008, San Francisco, California, USA.
Martin Kutz and Pascal Schweitzer:
ScrewBox: a Randomized Certifying Graph Non-Isomorphism Algorithm.
In Proceedings of ALENEX 2007, New Orleans, Lousiana, USA.
[ps] [pdf] (preliminary version)
Rolf Klein and Martin Kutz:
Computing Geometric Minimum-Dilation Graphs is NP-hard.
In Proceedings of Graph Drawing 2006, Karlsruhe, Germany, 2006.
[ps] [pdf]
Gerth Stølting Brodal, Kanela Kaligosi, Irit Katriel, and Martin Kutz:
Faster Algorithms for Computing Longest Commmon Increasing Subsequences.
In Proceedings of CPM 2006, Barcelona, Spain, 2006, pp. 330-341.
[ps] [pdf]
Martin Kutz:
Computing Shortest Non-Trivial Cycles on Orientable Surfaces of Bounded Genus in Almost Linear Time.
In Proceedings of SoCG 2006, Sedona, Arizona, USA, 2006, pp. 430-437.
[ps] [pdf]
Rolf Klein, and Martin Kutz:
The Density of Iterated Crossing Points and a Gap Result for Triangulations of Finite Point Sets.
In Proceedings of SoCG 2006, Sedona, Arizona, USA, 2006, pp. 264-272.
[ps] [pdf]
Khaled Elbassioni, Irit Katriel, Martin Kutz, and Meena Mahajan:
Simultaneous Matchings.
In Proceedings of ISAAC 2005, Sanya, Hainan, China, 2005, pp. 106-115.
[ps] [pdf] © Springer-Verlag
Martin Kutz:
Weak Positional Games on Hypergraphs of Rank Three.
In Proceedings of EuroComb 2005, Berlin, Germany, 2005, pp. 31-36.
[ps] [pdf]
Martin Kutz and Attila Pór:
Angel, Devil, and King.
In Proceedings of COCOON 2005, Kunming, China, 2005, pp. 925-934
[ps] [pdf] © Springer-Verlag
Kaspar Fischer, Bernd Gärtner, and Martin Kutz:
Fast Smallest-Enclosing-Ball Computation in High Dimensions.
In Proceedings of The 11th Annual European Symposium on Algorithms (ESA 2003), Budapest, Hungary, 2003, pp. 630-641.
[ps] [pdf] © Springer-Verlag
Martin Kutz:
The Complexity of Boolean Matrix Root Computation.
In Proceedings of The 9th Annual International Conference on Computing and Combinatorics (COCOON 2003), Big Sky, Montana, USA, 2003, pp. 212-221.
[ps] [pdf] © Springer-Verlag
Manuel Bodirsky and Martin Kutz:
Pure Dominance Constraints.
In Proceedings of The 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2002), Antibes - Juan les Pins, France, 2002, pp. 287-298.
[ps] [pdf] © Springer-Verlag

Manuscripts / TechReports

Irit Katriel, Martin Kutz, and Martin Skutella:
Reachability Substitutes for Planar Digraphs.
[ps]
Manuel Bodirsky and Martin Kutz:
Determining the Consistency of Partial Tree Descriptions.
[ps] [pdf]

Theses

Ph.D. thesis:
The Angel Problem, Positional Games, and Digraph Roots.
Advisor: Martin Aigner.
Freie Universität Berlin, 2004.
Diploma thesis:
Grundlegende Betrachtungen zu einer Variante von Additionsketten.
(in German, "basic considerations about a variant of addition chains")
Advisor: Arnold Schönhage.
Rheinische Friedrich-Wilhelms Universität Bonn, 2000.