2 papers
cs.DS2026
A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
Thekla Hamm, Sukanya Pandey, Krisztina Szilágyi
Given a planar graph, a subset of its vertices called terminals, and , the Face Cover Number problem asks whether the terminals lie on the boundaries of at most $…
cs.CC2025
Oracle Separations for RPH
Thekla Hamm, Lucas Meijer, Tillmann Miltzow +1
While theoretical computer science primarily works with discrete models of computation, like the Turing machine and the wordRAM, there are many scenarios in which introducing real…