Time-space trade-offs in population protocols for the majority problem (2020)
Journal Article
Berenbrink, P., Elsässer, R., Friedetzky, T., Kaaser, D., Kling, P., & Radzik, T. (2021). Time-space trade-offs in population protocols for the majority problem. Distributed Computing, 34(2), 91-111. https://doi.org/10.1007/s00446-020-00385-0

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion w... Read More about Time-space trade-offs in population protocols for the majority problem.

Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy (2020)
Journal Article
Bonamy, M., Bousquet, N., Dabrowski, K., Johnson, M., Paulusma, D., & Pierron, T. (2021). Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy. Algorithmica, 83(3), 822-852. https://doi.org/10.1007/s00453-020-00747-x

We resolve the computational complexity of GRAPH ISOMORPHISM for classes of graphs characterized by two forbidden induced subgraphs H_{1} and H_2 for all but six pairs (H_1,H_2). Schweitzer had previously shown that the number of open cases was finit... Read More about Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy.

The Power of Linear-Time Data Reduction for Maximum Matching (2020)
Journal Article
Mertzios, G., Nichterlein, A., & Niedermeier, R. (2020). The Power of Linear-Time Data Reduction for Maximum Matching. Algorithmica, 82(12), 3521-3565. https://doi.org/10.1007/s00453-020-00736-0

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For m-edge and n-vertex graphs, it is well-known to be solvable in O(mn−−√) time; however, for several applications this running time is... Read More about The Power of Linear-Time Data Reduction for Maximum Matching.

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.

How fast can we reach a target vertex in stochastic temporal graphs? (2020)
Journal Article
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Raptopoulos, C., Spirakis, P. G., & Zmaraev, V. (2020). How fast can we reach a target vertex in stochastic temporal graphs?. Journal of Computer and System Sciences, 114, 65-83. https://doi.org/10.1016/j.jcss.2020.05.005

Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with G as the underlying graph is a sequence of subgraphs (snapshots) of G, where . In this paper we study stochastic temporal graphs, i.e. stoc... Read More about How fast can we reach a target vertex in stochastic temporal graphs?.

Disconnected cuts in claw-free graphs (2020)
Journal Article
Martin, B., Paulusma, D., & van Leeuwen, E. (2020). Disconnected cuts in claw-free graphs. Journal of Computer and System Sciences, 113, 60-75. https://doi.org/10.1016/j.jcss.2020.04.005

A disconnected cut of a connected graph is a vertex cut that itself also induces a disconnected subgraph. The corresponding decision problem is called Disconnected Cut. This problem is known to be NP-hard on general graphs. We prove that it is polyno... Read More about Disconnected cuts in claw-free graphs.

Clique-width for graph classes closed under complementation (2020)
Journal Article
Blanché, A., Dabrowski, K., Johnson, M., Lozin, V., Paulusma, D., & Zamaraev, V. (2020). Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34(2), 1107-1147. https://doi.org/10.1137/18m1235016

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We study the boundedness of cliq... Read More about Clique-width for graph classes closed under complementation.

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, 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.

Colouring (Pr + Ps)-Free Graphs (2020)
Journal Article
Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2020). Colouring (Pr + Ps)-Free Graphs. Algorithmica, 82(7), 1833-1858. https://doi.org/10.1007/s00453-020-00675-w

The k-Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for a fixed integer k such that no two adjacent vertices are coloured alike. If each vertex u must be assigned a colour from a prescribed list L(u)... Read More about Colouring (Pr + Ps)-Free Graphs.

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest (2020)
Journal Article
Dabrowski, K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D., & Rzążewski, P. (2020). On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. Algorithmica, 82(10), 2841-2866. https://doi.org/10.1007/s00453-020-00706-6

A graph is H-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problems FEEDBACK VERTEX SET and ODD CYCLE TRANSVERSAL by showing that they can be solved in polynomial time... Read More about On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.