Polynomial-delay generation of functional digraphs up to isomorphism

We describe a procedure for the generation of functional digraphs up to isomorphism; these are digraphs with uniform outdegree 1, also called mapping patterns, finite endofunctions, or finite discrete-time dynamical systems. This procedure is based on a reverse search algorithm for the generation of...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2024-11, Vol.357, p.24-33
Main Authors: Defrain, Oscar, Porreca, Antonio E., Timofeeva, Ekaterina
Format: Article
Language:English
Subjects:
Algorithmic enumeration
Finite dynamical systems
Functional digraphs
Graph isomorphism
Reverse search
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We describe a procedure for the generation of functional digraphs up to isomorphism; these are digraphs with uniform outdegree 1, also called mapping patterns, finite endofunctions, or finite discrete-time dynamical systems. This procedure is based on a reverse search algorithm for the generation of connected functional digraphs, which is then applied as a subroutine for the generation of arbitrary ones. Both algorithms output solutions with O(n2) delay and require linear space with respect to the number n of vertices.
ISSN:0166-218X
DOI:10.1016/j.dam.2024.05.030