Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
On the parameterized complexity of Broadcast Independence and Broadcast Packing
Joanne Dumont, Edouard Nemery, Anthony Perez +1
A broadcast on a connected graph is a function f that assigns each vertex v an integer f(v) with 0 <= f(v) <= ecc(v) where ecc(v) denotes the eccentricity of v. A vertex u hears a…
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…