Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

20.12.2019

Paper accepted at STACS

Starting as a French-German collaboration, the International Symposium on Theoretical Aspects of Computer Science (STACS) is now one of the most renown European conference in TCS. The Algorithm Engineering group contributes one paper to its next edition on March 10-13, 2020 in Montpellier, France. In this work, Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann show that the NP-complete Vertex Cover problem can be solved in polynomial time with high probability on hyperbolic random graphs, which are a good model for real-world social networks.

  • Solving Vertex Cover in P... - Download
    Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. Symposium on the Theoretical Aspects of Computer Science (STACS) 2020