Paper Info
Title
Implicit Generation Of Pattern-Avoiding Permutations By Using Permutation Decision Diagrams
Abstract
Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure pi DDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.
Year
DOI
Venue
2014
10.1587/transfun.E97.A.1171
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
Field
DocType
pattern-avoiding permutations, generating algorithms, decision diagrams, pi DD, experimental algorithms
Discrete mathematics,Permutation,Random permutation statistics,Theoretical computer science,Mathematics
Journal
Volume
Issue
ISSN
E97A
6
0916-8508
Citations 
PageRank 
References 
0
0.34
9
Authors
3
Name
Order
Citations
PageRank
Yuma Inoue132.44
Takahisa Toda2113.53
Shin-ichi Minato372584.72