Constant time and space updates for the sigma-tau problem

DOI10.1007/978-3-031-43980-3_26MaRDI QIDQ6545441FDOQ6545441

Authors Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro, Aaron Williams

Publication date 29 May 2024

zbMATH Keywords

permutationsdynamic data structurescombinatorial generationcombinatorial Gray codessigma-tau problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• Solving the sigma-tau problem
• scientific article; zbMATH DE number 6850346
• Syntactic view of sigma-tau generation of permutations
• Syntactic view of sigma-tau generation of permutations
• An explicit universal cycle for the (n-1)-permutations of an n-set

Cites work

• Title not available (Why is no real title available?)
• scientific article; zbMATH DE number 3557795 (Why is no real title available?)
• scientific article; zbMATH DE number 1263193 (Why is no real title available?)
• scientific article; zbMATH DE number 6850346 (Why is no real title available?)
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• scientific article; zbMATH DE number 7051269 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 2230164 (Why is no real title available?)
• scientific article; zbMATH DE number 3046846 (Why is no real title available?)
• A Simple Proof of Rankin's Campanological Theorem
• A Survey of Combinatorial Gray Codes
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• Combinatorial Gray codes -- an updated survey
• Combinatorics of genome rearrangements.
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Containing all permutations
• Doubly adjacent gray codes for the symmetric group
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Faster entropy-bounded compressed suffix trees
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Genome Rearrangements and Sorting by Reversals
• Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
• Indexing compressed text
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• Permutation patterns in genome rearrangement problems: the reversal model
• Shorthand universal cycles for permutations
• Solving the sigma-tau problem
• Sorting by Transpositions
• Succinct representations of permutations and functions
• Syntactic view of sigma-tau generation of permutations
• The coolest way to generate combinations
• r-indexing the eBWT

Cited in

(2)

• Generating signed permutations by twisting two-sided ribbons
• On the hardness of Gray code problems for combinatorial objects

This page was built for publication: Constant time and space updates for the sigma-tau problem

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