Decompositions of graphs of functions and fast iterations of lookup tables

DOI10.1016/J.DAM.2006.06.006MaRDI QIDQ868394zbMATH OpenOpenAlexFDO

Authors Boaz Tsaban

Publication date 2 March 2007

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

Full work available at URL https://doi.org/10.1016/j.dam.2006.06.006

zbMATH Keywords

cycle decompositioncycle structurefast forward functionsfast forward permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial probability (60C05) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Cryptography (94A60)

Recommendations

• Complexity of computation of some functions of graphs
• scientific article; zbMATH DE number 1287928
• scientific article; zbMATH DE number 706829
• Fast searching on Cartesian products of graphs
• Use of partial substitutions for time decomposition of Boolean functions and generalized graph schemes of algorithms
• Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• scientific article; zbMATH DE number 1472110
• scientific article; zbMATH DE number 46126
• Decomposition of graphs and monotone formula size of homogeneous functions

Cites work

• Constructing pseudo-random permutations with a prescribed structure
• On the implementation of huge random objects
• Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation

Cited in

(1)

• Efficient computation of the iteration of functions

This page was built for publication: Decompositions of graphs of functions and fast iterations of lookup tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868394)