[ Universität Bonn | Institut für Informatik | Abteilung V | deutsche Version ]

Dr. Mikael Gast Postdoc Department of Computer Science and Hausdorff Center for Mathematics, HCM University of Bonn Friedrich-Ebert-Allee 144 53113 Bonn Email:  gast (ät) cs.uni-bonn.de Phone: +49 228 734209 Fax: +49 228 734440

Publications

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


• Approximability of TSP in Power Law Graphs
  Joint work with Mathias Hauptmann and Marek Karpinski,
  in Computing Research Repository (CoRR), arXiv:1509.03976, 2015;
  


• Inapproximability of Dominating Set in Power Law Graphs
  Joint work with Mathias Hauptmann and Marek Karpinski,
  in Theoretical Computer Science 562, pp. 436-452, 2015 (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 Mathias Hauptmann and Marek Karpinski,
  Computing Research Repository (CoRR), arXiv:1210.2698, 2012


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


• Efficient Parallel Computation of Nearest Neighbor Interchange Distances
  Joint work with Mathias Hauptmann,
  Computing Research Repository (CoRR), arXiv:1205.3402, 2012 (talk)

Talks

• Approximability of Combinatorial Optimization Problems on Power Law Networks
  (slides), Bonn, September 4, 2013