New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings

DOI10.4230/LIPICS.STACS.2014.162MaRDI QIDQ2965481zbMATH OpenOpenAlexFDO

Authors M. Bodnar, Benjamin De Winkle, F. Blanchet-Sadri

Publication date 3 March 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2014/4455/pdf/13.pdf

zbMATH Keywords

undirected graphsindeterminate stringspartial wordsborder arraysprefix arrays

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorics on words (68R15)

Recommendations

• New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
• Indeterminate strings, prefix arrays \& undirected graphs
• Inferring an indeterminate string from a prefix graph
• Representing prefix and border tables: results on enumeration
• On the number of prefix and border tables

Cited in

(8)

• Universal reconstruction of a string
• Combinatorics on partial word borders
• Indeterminate strings, prefix arrays \& undirected graphs
• Border correlations, lattices, and the subgraph component polynomial
• On the number of prefix and border tables
• New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings
• A prefix array for parameterized strings
• Inferring an indeterminate string from a prefix graph

This page was built for publication: New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings

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