38 citations · 99 across the 20 of their papers we have counts for
4 papers · 1 filter
Graphs with Bounded Push-Pop Walk Orderings
Antoine Amarilli, Claire David, Nadime Francis +3
Consider a directed graph G and the (generally infinite) set Walks(G) of the walks in that graph. We are interested in ordering Walks(G) as w1, w2,... in a way that ensures that ea…
Path Length Existence Problems in Bounded-Treewidth Probabilistic Graphs
Antoine Amarilli, Mikaël Monet, Harshul Sagar
We consider the problem of computing the probability of existence of a source-to-target path or walk satisfying a given length constraint in an input probabilistic graph. The lengt…
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 ,…