Graph connectivity, partial words, and a theorem of Fine and Wilf

DOI10.1016/j.ic.2007.11.007zbMath1146.68408OpenAlexW2059464604MaRDI QIDQ924728

Gautam Sisodia, Deepak Bal, Francine Blanchet-Sadri

Publication date: 19 May 2008

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2007.11.007

zbMATH Keywords

wordsperiodsgraph connectivitypartial wordsfine and wilf's theorem

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items

String Periods in the Order-Preserving Model, Periods in partial words: an algorithm, The three-squares lemma for partial words with one hole, Periodicity properties on partial words, FINE AND WILF'S THEOREM FOR PARTIAL WORDS WITH ARBITRARILY MANY WEAK PERIODS, String periods in the order-preserving model, A periodicity lemma for partial words

Uses Software

• PatternHunter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalised fine and Wilf's theorem for arbitrary number of periods
• A periodicity result of partial words with one hole
• Improved algorithms for graph four-connectivity
• A probabilistic algorithm for vertex connectivity of graphs
• On the combinatorics of finite words
• Fine and Wilf's theorem for three periods and a generalization of Sturmian words
• Partial words and a theorem of Fine and Wilf
• Some combinatorial properties of Sturmian words
• Sturmian words: structure, combinatorics, and their arithmetics
• Sturmian words, Lyndon words and trees
• Periodicity on partial words
• Fine and Wilf words for any periods
• On spaced seeds for similarity search
• On a paper by Castelli, Mignosi, Restivo
• FINE AND WILF'S THEOREM FOR PARTIAL WORDS WITH ARBITRARILY MANY WEAK PERIODS
• On computing the connectivities of graphs and digraphs
• Fully Dynamic Algorithms for 2-Edge Connectivity
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• Network Flow and Testing Graph Connectivity
• Partial words and the interaction property of periods
• Dividing a Graph into Triconnected Components
• Computing Vertex Connectivity: New Bounds from Old Techniques
• Uniqueness Theorems for Periodic Functions
• DNA Computing
• Depth-First Search and Linear Graph Algorithms
• Combinatorial Pattern Matching
• Automata, Languages and Programming
• Partial words and a theorem of Fine and Wilf revisited