Indeterminate strings, prefix arrays \& undirected graphs

DOI10.1016/j.tcs.2015.06.056zbMath1329.68309arXiv1406.3289OpenAlexW1541587921MaRDI QIDQ496001

Manolis Christodoulakis, W. F. Smyth, Shu Wang, Patrick J. Ryan

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.3289

zbMATH Keywords

undirected graphlexicographical orderfeasible arrayindeterminate stringminimum alphabet sizeprefix arrayprefix tableregular string

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Algorithms on strings (68W32)

Related Items

New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings, Universal Reconstruction of a String, Computing covers using prefix tables, Border correlations, lattices, and the subgraph component polynomial, Border Correlations, Lattices, and the Subgraph Component Polynomial, Reconstructing a string from its Lyndon arrays, Constructing an indeterminate string from its associated graph, A new approach to regular \& indeterminate strings, A prefix array for parameterized strings, An improved upper bound and algorithm for clique covers, Universal reconstruction of a string, Inferring an indeterminate string from a prefix graph

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new approach to the periodicity lemma on strings with holes
• Fast pattern-matching on indeterminate strings
• Prefix Table Construction and Conversion
• An O(n log n) algorithm for finding all repetitions in a string
• RECONSTRUCTING A SUFFIX ARRAY
• AN ADAPTIVE HYBRID PATTERN-MATCHING ALGORITHM ON INDETERMINATE STRINGS
• Generalized String Matching
• Algorithmic Combinatorics on Partial Words
• REVERSE ENGINEERING PREFIX TABLES
• Mathematical Foundations of Computer Science 2003
• Algorithms on Strings
• Depth-First Search and Linear Graph Algorithms
• Algorithm 457: finding all cliques of an undirected graph
• Sur le coloriage des graphs
• On cliques in graphs
• Partial words and a theorem of Fine and Wilf revisited