38 citations · 63 across the 11 of their papers we have counts for
4 papers · 1 filter
The S-Hamiltonian Cycle Problem
Antoine Amarilli, Arthur Lombardo, Mikaël Monet
Determining if an input undirected graph is Hamiltonian, i.e., if it has a cycle that visits every vertex exactly once, is one of the most famous NP-complete problems. We consider…
Gray Codes With Constant Delay and Constant Auxiliary Space
Antoine Amarilli, Claire David, Nadime Francis +3
We give the first two algorithms to enumerate all binary words of (like Gray codes) while ensuring that the delay and the auxiliary space is independent from ,…
Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
Antoine Amarilli, Mikaël Monet, Rémi De Pretto
In this note, we study two rewrite rules on hypergraphs, called edge-domination and node-domination, and show that they are confluent. These rules are rather natural and commonly u…
A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
Antoine Amarilli, Marcelo Arenas, YooJung Choi +3
This document is an introduction to two related formalisms to define Boolean functions: binary decision diagrams, and Boolean circuits. It presents these formalisms and several of…