92 citations · 359 across the 37 of their papers we have counts for
5 papers · 1 filter
Identifying codes in vertex-transitive graphs and strongly regular graphs
Sylvain Gravier, Aline Parreau, Sara Rottey +2
We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1…
Deciding game invariance
Eric Duchêne, Aline Parreau, Michel Rigo
Duchêne and Rigo introduced the notion of invariance for take-away games on heaps. Roughly speaking, these are games whose rulesets do not depend on the position. Given a sequence…
Identifying codes in hereditary classes of graphs and VC-dimension
Nicolas Bousquet, Aurélie Lagoutte, Zhentao Li +2
An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We show a dichot…
A new approach to the -regularity of the -abelian complexity of -automatic sequences
Aline Parreau, Michel Rigo, Eric Rowland +1
We prove that a sequence satisfying a certain symmetry property is -regular in the sense of Allouche and Shallit, i.e., the -module generated by its -kernel is fi…
Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
Florent Foucaud, George B. Mertzios, Reza Naserasr +2
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets (denoted IDENTIFYING CODE, (OPEN) LOCATING-DOMINATING SET and METR…