A construction of short sequences containing all permutations of a set as subsequences

Saša Radomirović

doi:10.37236/2859

A construction of short sequences containing all permutations of a set as subsequences

Saša Radomirović^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

14 Citations (Scopus)

Abstract

A sequence over a fixed finite set is said to be complete if it contains all per- mutations of the set as subsequences. Determining the length of shortest complete sequences is an open problem. We improve the existing upper bound and introduce tools to manually prove the completeness of sequences.

Original language	English
Article number	P31
Journal	Electronic Journal of Combinatorics
Volume	19
Issue number	4
DOIs	https://doi.org/10.37236/2859
Publication status	Published - 22 Nov 2012

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/2859

Cite this

@article{b053764c6fc4488e886892b232de0284,

title = "A construction of short sequences containing all permutations of a set as subsequences",

abstract = "A sequence over a fixed finite set is said to be complete if it contains all per- mutations of the set as subsequences. Determining the length of shortest complete sequences is an open problem. We improve the existing upper bound and introduce tools to manually prove the completeness of sequences.",

author = "Sa{\v s}a Radomirovi{\'c}",

year = "2012",

month = nov,

day = "22",

doi = "10.37236/2859",

language = "English",

volume = "19",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "4",

}

TY - JOUR

T1 - A construction of short sequences containing all permutations of a set as subsequences

AU - Radomirović, Saša

PY - 2012/11/22

Y1 - 2012/11/22

N2 - A sequence over a fixed finite set is said to be complete if it contains all per- mutations of the set as subsequences. Determining the length of shortest complete sequences is an open problem. We improve the existing upper bound and introduce tools to manually prove the completeness of sequences.

AB - A sequence over a fixed finite set is said to be complete if it contains all per- mutations of the set as subsequences. Determining the length of shortest complete sequences is an open problem. We improve the existing upper bound and introduce tools to manually prove the completeness of sequences.

UR - http://www.scopus.com/inward/record.url?scp=84870223481&partnerID=8YFLogxK

U2 - 10.37236/2859

DO - 10.37236/2859

M3 - Article

AN - SCOPUS:84870223481

SN - 1077-8926

VL - 19

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

M1 - P31

ER -

A construction of short sequences containing all permutations of a set as subsequences

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this