Alice Joffard

dblp:220/3936 · DBLP profile ↗
← Back
4ranked-venue papers
0as first author
2since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 2 since 2021Applied, interdisciplinary, general and emerging computing · 1
YearPublicationVenuePosition
2021 TS-Reconfiguration of Dominating Sets in Circle and Circular-Arc Graphs
Nicolas Bousquet 0001, Alice Joffard
FCT2
2021 Eternal dominating sets on digraphs and orientations of graphs
Guillaume Bagan, Alice Joffard, Hamamache Kheddouci
Discret. Appl. Math.2
2020 Linear Transformations Between Dominating Sets in the TAR-Model
abstract
Given a graph G and an integer k, a token addition and removal (TAR for short) reconfiguration sequence between two dominating sets D_s and D_t of size at most k is a sequence S = ⟨ D₀ = D_s, D₁ …, D_𝓁 = D_t ⟩ of dominating sets of G such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than k. We first improve a result of Haas and Seyffarth [R. Haas and K. Seyffarth, 2017], by showing that if k = Γ(G)+α(G)-1 (where Γ(G) is the maximum size of a minimal dominating set and α(G) the maximum size of an independent set), then there exists a linear TAR reconfiguration sequence between any pair of dominating sets. We then improve these results on several graph classes by showing that the same holds for K_𝓁-minor free graph as long as k ≥ Γ(G)+O(𝓁 √(log 𝓁)) and for planar graphs whenever k ≥ Γ(G)+3. Finally, we show that if k = Γ(G)+tw(G)+1, then there also exists a linear transformation between any pair of dominating sets.
Nicolas Bousquet 0001, Alice Joffard, Paul Ouvrard
ISAAC2
2020 Approximating Shortest Connected Graph Transformation for Trees
Nicolas Bousquet 0001, Alice Joffard
SOFSEM2