Polynomial-delay generation of functional digraphs up to isomorphism

DOI10.1016/j.dam.2024.05.030zbMath1547.05106MaRDI QIDQ6611003

Oscar Defrain, Ekaterina Timofeeva, Antonio E. Porreca

Publication date: 26 September 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

finite dynamical systemsgraph isomorphismreverse searchfunctional digraphsalgorithmic enumeration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On random mapping patterns
• An efficient algorithm for solving pseudo clique enumeration problem
• On generating all maximal independent sets
• Lexicographically least circular substrings
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Reverse search for enumeration
• Practical graph isomorphism. II.
• On enumerating minimal dicuts and strongly connected subgraphs
• Constant Time Enumeration of Bounded-Size Subtrees in Trees and Its Application
• Constant Time Generation of Rooted Trees
• Efficient algorithms for listing unlabeled graphs
• Isomorph-Free Exhaustive Generation
• A Polynomial Delay Algorithm for Generating Connected Induced Subgraphs of a Given Cardinality
• Polynomial Equations over Finite, Discrete-Time Dynamical Systems

This page was built for publication: Polynomial-delay generation of functional digraphs up to isomorphism