Mostrar el registro sencillo del ítem
dc.contributor.author
Becher, Veronica Andrea
dc.contributor.author
Cortés, Lucas
dc.date.available
2022-10-21T12:35:22Z
dc.date.issued
2021-06
dc.identifier.citation
Becher, Veronica Andrea; Cortés, Lucas; Extending de Bruijn sequences to larger alphabets; Elsevier Science; Information Processing Letters; 168; 6-2021; 1-6
dc.identifier.issn
0020-0190
dc.identifier.uri
http://hdl.handle.net/11336/174303
dc.description.abstract
A de Bruijn sequence of order n over a k-symbol alphabet is a circular sequence where each length-n sequence occurs exactly once. We present a way of extending de Bruijn sequences by adding a new symbol to the alphabet: the extension is performed by embedding a given de Bruijn sequence into another one of the same order, but over the alphabet with one more symbol, while ensuring that there are no long runs without the new symbol. Our solution is based on auxiliary graphs derived from the de Bruijn graph and solving a problem of maximum flow.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
COMBINATORIAL PROBLEMS
dc.subject
DE BRUIJN SEQUENCES
dc.subject
EULERIAN CYCLE
dc.subject
GRAPH ALGORITHMS
dc.subject
MAXIMUM FLOW
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Extending de Bruijn sequences to larger alphabets
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2022-09-22T16:15:48Z
dc.journal.volume
168
dc.journal.pagination
1-6
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Becher, Veronica Andrea. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación; Argentina
dc.description.fil
Fil: Cortés, Lucas. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina
dc.journal.title
Information Processing Letters
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2020.106085
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0020019020301721
Archivos asociados