3 papers
cs.DS2026
Almost Linear 3-Spanners of Temporal Cliques
Julia Baligacs, Davide Bilò, Václav Blažej +2
Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in…
cs.DS2025
Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors
Clément Dallard, Maël Dumas, Claire Hilaire +1
The -Induced Minor Containment problem (-IMC) consists in deciding if a fixed graph is an induced minor of a graph given as input, that is, whether can be obtaine…
cs.DS2021
A cubic vertex-kernel for Trivially Perfect Editing
Maël Dumas, Anthony Perez, Ioan Todinca
We consider the Trivially Perfect Editing problem, where one is given an undirected graph and a parameter and seeks to edit (add or delete) at most $…