[ Universität Bonn | Institut für Informatik | Abteilung V | english version ]

Mathias Hauptmann Raum II.70 Institut für Informatik V Universität Bonn Friedrich-Ebert-Allee 144 53113 Bonn Germany Email:  hauptman followed by at cs.uni-bonn.de Telefon: +49 228 734319 Fax: +49 228 734440

Veröffentlichungen

• On Bounded Nondeterminism and Alternation
  Preprint, 2016


• On Alternation and the Union Theorem
  Computing Research Repository (CoRR), arXiv:1602.047816, 2016


• Approximation Complexity of Max-Cut on Power Law Graphs
  Joint work with Mikael Gast and Marek Karpinski
  Computing Research Repository (CoRR), arXiv:1602.08369, 2016


• Approximability of TSP on Power Law Graphs
  Joint work with Mikael Gast and Marek Karpinski
  Computing Research Repository (CoRR), arXiv:1509.03976, 2015


• On the Approximability of Independent Set Problem on Power Law Graphs
  Joint work with Marek Karpinski
  Computing Research Repository (CoRR), arXiv:1503.02880, 2015


• Inapproximability of Dominating Set in Power Law Graphs
  Joint work with Mikael Gast and Marek Karpinski
  in Theoretical Computer Science (2014), http://dx.doi.org/10.1016/j.tcs.2014.10.021
  


• Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations
  Joint work with Mikael Gast and Marek Karpinski
  Computing Research Repository (CoRR), arXiv:1210.2698, 2012


• Approximability of the Vertex Cover Problem in Power Law Graphs
  Joint work with Mikael Gast
  in Theoretical Computer Science 516, pp. 60-70, 2014 (ps, pdf).


• On Approximation Complexity of Metric Dimension Problem
  Joint work with Claus Viehmann and Richard Schmied,
  In Proc. 21st IWOCA 2010, LNCS 6460, pp. 136-139, 2011;
  also appeared in Journal of Discrete Algorithms 14, pp. 214-222, 2012 (ps, pdf).


• Efficient Parallel Computation of Nearest Neighbor Interchange Distances
  Joint work with Mikael Gast
  Computing Research Repository (CoRR), arXiv:1205.3402, 2012.


• Scaled Dimension and the Berman-Hartmanis Conjecture
  CS-Report 85230, 2008 (ps, pdf).


• Approximability of Selected Phylogenetic Tree Problems
  Joint work with Marlis Lamp,
  CS-Report 85299, 2008 (ps, pdf)


• Polynomial Approximation Schemes for Dense and Geometric k-Restricted Steiner Forest Problems
  Joint work with Claus Viehmann, Sören Kühl, and Richard Schmied,
  CS-Report 85288, 2008 (ps, pdf).


• On the Approximability of Dense Steiner Problems
  In Proc. 10th ICTCS 2007, pp. 15-26;
  also appeared in Journal of Discrete Algorithms 21, pp. 41-51, 2013.


• The Measure Hypothesis and Efficiency of Polynomial Time Approximation Schemes
  In Proc. 10th ICTCS 2007, pp. 151-162.


• Approximation Hardness of the (1,2)-Steiner Tree Problem
  CS-Report 85283, 2007 (ps, pdf).

Recent Talks

• On the Approximability of Independent Set Problem in Power Law Graphs
  ( slides), Oberseminar Theoretische Informatik, University of Bonn, July 08, 2015.


• Approximability of the TSP on Power Law Graphs
  ( slides), Oberseminar Theoretische Informatik, University of Bonn, July 29, 2015.