Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Moderately beyond clique-width: reduced component max-leaf and related parameters
Ãdouard Bonnet, Yeonsu Chang, Julien Duron +2
Reduced parameters [BKW, JCTB '26; BKRT, SODA '22] are defined via contraction sequences. Based on this framework, we introduce the reduced component max-leaf, denoted by $\operato…
cs.DS2025
Maximum Independent Set when excluding an induced minor: and
Ãdouard Bonnet, Julien Duron, Colin Geniet +2
Dallard, MilaniÄ, and Å torgel [arXiv '22] ask if for every class excluding a fixed planar graph as an induced minor, Maximum Independent Set can be solved in polynomial time,…
cs.DS2024
Symmetric-Difference (Degeneracy) and Signed Tree Models
Ãdouard Bonnet, Julien Duron, John Sylvester +1
We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-diffe…