Home
Hasso-Plattner-Institut
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

schließen

schließen

schließen

schließen

schließen

schließen

schließen

schließen
  1. soda-stacs

10.03.2025

Three Papers accepted at SODA and STACS

We are happy to announce three great papers that were recently accepted: First, Kirill Simonov wrote the paper Packing Short Cycles for the Symposium on Discrete Algorithms (SODA) which took place on 12-15 January in New Orleans, USA, together with co-authors he met at a workshop. In the paper, they show that, given a weighted undirected graph, one can find k vertex-disjoint cycles of minimum total length in polynomial time, for every fixed k. Moreover, when looking for k vertex-disjoint cycles where each cycle is shortest in the graph, for planar graphs there exists an FPT algorithm parameterized by k.

The second paper was written by Janosch Ruff with Samuel Baguley and George Skretas and Yannic Maus for the International Symposium on Theoretical Aspects of Computer Science (STACS) which took place on 4-7 March in Jena, Germany. It it titled Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring. In contrast to the theoretical worst case analysis, algorithms often perform much better in practice even using very simple heuristics. In an attempt to explain this theory-practice gap, it is shown in the paper that for the notoriously (NP-)hard problem of colouring, a greedy algorithms performs very well on graphs that have properties one often finds in real-world networks.

And finally, by Shaily Verma and various co-authors there is the paper Parameterized Saga of First-Fit and Last-Fit Coloring. The authors investigate the parameterized complexity of Grundy and partial Grundy coloring problems, which correspond to the worst-case performance of the First-Fit and Last-Fit coloring heuristics, respectively. They design FPT algorithms for these problems under various graph parameters, offering new insights into the efficiency and limitations of graph coloring strategies.

  • Hyperbolic Random Graphs:... - Download
    Baguley, Samuel; Maus, Yannic Maus; Ruff, Janosch; Skretas, George Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for ColouringInternational Symposium on Theoretical Aspects of Computer Science (STACS) 2025: 13:1–13:20
    [ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]