Ranking, unranking and random generation of extensional acyclic digraphs

Ranking, unranking and random generation of extensional acyclic digraphs

0.00 Avg rating0 Votes
Article ID: iaor20131577
Volume: 113
Issue: 5-6
Start Page Number: 183
End Page Number: 187
Publication Date: Mar 2013
Journal: Information Processing Letters
Authors: ,
Keywords: optimization, computers: data-structure
Abstract:

Extensional acyclic digraphs are acyclic digraphs whose vertices have pairwise different sets of out‐neighbors; they represent hereditarily finite sets, which stand at the basis of some computer languages. In this paper we give an O ( n 3 ) equ1 algorithm for generating uniformly at random an extensional acyclic digraph on n vertices. This is done by first proposing a linear‐time algorithm for encoding such digraphs by particular ( n 1 ) equ2‐tuples of subsets of { 0 , , n 2 } equ3. We then give a new counting recurrence for such tuples, which we exploit in ranking/unranking algorithms. These are also useful for indexing data structures by hereditarily finite sets.

Reviews

Required fields are marked *. Your email address will not be published.