Skip to main content

Research Repository

Advanced Search

Dr Maximilien Gadouleau's Outputs (39)

Generalising the maximum independent set algorithm via Boolean networks (2025)
Journal Article
Gadouleau, M., & Kutner, D. C. (2025). Generalising the maximum independent set algorithm via Boolean networks. Information and Computation, 303, Article 105266. https://doi.org/10.1016/j.ic.2025.105266

A simple greedy algorithm to find a maximal independent set (MIS) in a graph starts with the empty set and visits every vertex, adding it to the set if and only if none of its neighbours are already in the set. In this paper, we consider the generali... Read More about Generalising the maximum independent set algorithm via Boolean networks.

Graphs with minimum degree-entropy (2024)
Journal Article
Dong, Y., Gadouleau, M., Wan, P., & Zhang, S. (2024). Graphs with minimum degree-entropy. Information Sciences, 671, 120629. https://doi.org/10.1016/j.ins.2024.120629

We continue studying extremal values of the degree-entropy, which is an information-theoretic measure defined as the Shannon entropy based on the information functional involving vertex degrees. For a graph with a given number of vertices and edges a... Read More about Graphs with minimum degree-entropy.

Factorisation in the semiring of finite dynamical systems (2024)
Journal Article
Naquin, É., & Gadouleau, M. (2024). Factorisation in the semiring of finite dynamical systems. Theoretical Computer Science, 998, Article 114509. https://doi.org/10.1016/j.tcs.2024.114509

Finite dynamical systems (FDSs) are commonly used to model systems with a finite number of states that evolve deterministically and at discrete time steps. Considered up to isomorphism, those correspond to functional graphs. As such, FDSs have a sum... Read More about Factorisation in the semiring of finite dynamical systems.

The MacWilliams Identity for the Skew Rank Metric (2023)
Journal Article
Friedlander, I., Bouganis, A., & Gadouleau, M. (2025). The MacWilliams Identity for the Skew Rank Metric. Advances in Mathematics of Communications, 19(1), 140-179. https://doi.org/10.3934/amc.2023045

The weight distribution of an error correcting code is a crucial statistic in determining its performance. One key tool for relating the weight of a code to that of it's dual is the MacWilliams Identity, first developed for the Hamming metric. This i... Read More about The MacWilliams Identity for the Skew Rank Metric.

Graphs with minimum fractional domatic number (2023)
Journal Article
Gadouleau, M., Harms, N., Mertzios, G. B., & Zamaraev, V. (2024). Graphs with minimum fractional domatic number. Discrete Applied Mathematics, 343, 140-148. https://doi.org/10.1016/j.dam.2023.10.020

The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant of this notion. Graphs with fractional domatic number 1 are exactly th... Read More about Graphs with minimum fractional domatic number.

Bent functions in the partial spread class generated by linear recurring sequences (2022)
Journal Article
Gadouleau, M., Mariot, L., & Picek, S. (2023). Bent functions in the partial spread class generated by linear recurring sequences. Designs, Codes and Cryptography, 91(1), 63-82. https://doi.org/10.1007/s10623-022-01097-1

We present a construction of partial spread bent functions using subspaces generated by linear recurring sequences (LRS). We first show that the kernels of the linear mappings defined by two LRS have a trivial intersection if and only if their feedba... Read More about Bent functions in the partial spread class generated by linear recurring sequences.

Expansive automata networks (2020)
Journal Article
Bridoux, F., Gadouleau, M., & Theyssier, G. (2020). Expansive automata networks. Theoretical Computer Science, 843, 25-44. https://doi.org/10.1016/j.tcs.2020.06.019

An Automata Network is a map where Q is a finite alphabet. It can be viewed as a network of n entities, each holding a state from Q, and evolving according to a deterministic synchronous update rule in such a way that each entity only depends on its... Read More about Expansive automata networks.

Fixing monotone Boolean networks asynchronously (2020)
Journal Article
Aracena, J., Gadouleau, M., Richard, A., & Salinas, L. (2020). Fixing monotone Boolean networks asynchronously. Information and Computation, 274, Article 104540. https://doi.org/10.1016/j.ic.2020.104540

The asynchronous automaton associated with a Boolean network f : f0; 1gn ! f0; 1gn is considered in many applications. It is the nite deterministic automaton with set of states f0; 1gn, alphabet f1; : : : ; ng, where the action of letter i on a state... Read More about Fixing monotone Boolean networks asynchronously.

Elementary, finite and linear vN-regular cellular automata (2020)
Journal Article
Castillo-Ramirez, A., & Gadouleau, M. (2020). Elementary, finite and linear vN-regular cellular automata. Information and Computation, 274, Article 104533. https://doi.org/10.1016/j.ic.2020.104533

Let G be a group and A a set. A cellular automaton (CA) over AG is von Neumann regular (vN-regular) if there exists a CA over AG such that = , and in such case, is called a weak generalised inverse of . In this paper, we investigate vN-regularity of... Read More about Elementary, finite and linear vN-regular cellular automata.

Complete Simulation of Automata Networks (2019)
Journal Article
Bridoux, F., Castillo-Ramirez, A., & Gadouleau, M. (2020). Complete Simulation of Automata Networks. Journal of Computer and System Sciences, 109, 1-21. https://doi.org/10.1016/j.jcss.2019.12.001

Consider a finite set A and . We study complete simulation of transformations of , also known as automata networks. For , a transformation of is n-complete of size m if it may simulate every transformation of by updating one register at a time. Using... Read More about Complete Simulation of Automata Networks.

On the stability and instability of finite dynamical systems with prescribed interaction graphs (2019)
Journal Article
Gadouleau, M. (2019). On the stability and instability of finite dynamical systems with prescribed interaction graphs. Electronic Journal of Combinatorics, 26(3), Article P3.32

The dynamical properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding, and in the context of hat games, such as the guessing game and Winkler's hat game. The instability... Read More about On the stability and instability of finite dynamical systems with prescribed interaction graphs.

Max-flow min-cut theorems on dispersion and entropy measures for communication networks (2019)
Journal Article
Riis, S., & Gadouleau, M. (2019). Max-flow min-cut theorems on dispersion and entropy measures for communication networks. Information and Computation, 267, 49-73. https://doi.org/10.1016/j.ic.2019.03.004

The paper presents four distinct new ideas and results for communication networks: 1) We show that relay-networks (i.e. communication networks where different nodes use the same coding functions) can be used to model dynamic networks, in a way, vague... Read More about Max-flow min-cut theorems on dispersion and entropy measures for communication networks.

On the Rank and Periodic Rank of Finite Dynamical Systems (2018)
Journal Article
Gadouleau, M. (2018). On the Rank and Periodic Rank of Finite Dynamical Systems. Electronic Journal of Combinatorics, 25(3), Article #P3.48

A finite dynamical system is a function f:An→An where A is a finite alphabet, used to model a network of interacting entities. The main feature of a finite dynamical system is its interaction graph, which indicates which local functions depend on whi... Read More about On the Rank and Periodic Rank of Finite Dynamical Systems.

Finite Dynamical Systems, Hat Games, and Coding Theory (2018)
Journal Article
Gadouleau, M. (2018). Finite Dynamical Systems, Hat Games, and Coding Theory. SIAM Journal on Discrete Mathematics, 32(3), 1922-1945. https://doi.org/10.1137/15m1044758

The properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding and index coding, and in the context of hat games, such as the guessing game and Winkler's hat game. In this... Read More about Finite Dynamical Systems, Hat Games, and Coding Theory.

On the possible values of the entropy of undirected graphs (2017)
Journal Article
Gadouleau, M. (2018). On the possible values of the entropy of undirected graphs. Journal of Graph Theory, 88(2), 302-311. https://doi.org/10.1002/jgt.22213

The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contain... Read More about On the possible values of the entropy of undirected graphs.

Chains of subsemigroups (2017)
Journal Article
Cameron, P. J., Gadouleau, M., Mitchell, J. D., & Peresse, Y. (2017). Chains of subsemigroups. Israel Journal of Mathematics, 220(1), 479-508. https://doi.org/10.1007/s11856-017-1523-x

We investigate the maximum length of a chain of subsemigroups in various classes of semigroups, such as the full transformation semigroups, the general linear semigroups, and the semigroups of order-preserving transformations of finite chains. In som... Read More about Chains of subsemigroups.

Lengths of words in transformation semigroups generated by digraphs (2016)
Journal Article
Cameron, P. J., Castillo-Ramirez, A., Gadouleau, M., & Mitchell, J. D. (2017). Lengths of words in transformation semigroups generated by digraphs. Journal of Algebraic Combinatorics, 45(1), 149-170. https://doi.org/10.1007/s10801-016-0703-9

Given a simple digraph D on n vertices (with n≥2n≥2 ), there is a natural construction of a semigroup of transformations ⟨D⟩⟨D⟩ . For any edge (a, b) of D, let a→ba→b be the idempotent of rank n−1n−1 mapping a to b and fixing all vertices other than... Read More about Lengths of words in transformation semigroups generated by digraphs.

Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability (2016)
Journal Article
Gadouleau, M., Richard, A., & Fanchon, E. (2016). Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability. IEEE Transactions on Information Theory, 62(5), 2504-2519. https://doi.org/10.1109/tit.2016.2544344

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations towards their destinations. The solvability problem asks whether the demands of all the destination... Read More about Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability.

Simple dynamics on graphs (2016)
Journal Article
Gadouleau, M., & Richard, A. (2016). Simple dynamics on graphs. Theoretical Computer Science, 628, 62-77. https://doi.org/10.1016/j.tcs.2016.03.013

Can the interaction graph of a finite dynamical system force this system to have a “complex” dynamics? In other words, given a finite interval of integers A, which are the signed digraphs G such that every finite dynamical system f:An→An with G as in... Read More about Simple dynamics on graphs.