Combinatorial Pattern Matching: ... Annual SymposiumSpringer-Verlag, 1996 - Combinatorial analysis |
From inside the book
Results 1-3 of 11
Page 311
... Euler switch of P is a switch where the resulting set of 2 - paths defines an Euler path . Given an Euler path P and two nodes r and y , an Euler switch of P at nodes x , y yields an Euler path P containing exactly the same set of 2 ...
... Euler switch of P is a switch where the resulting set of 2 - paths defines an Euler path . Given an Euler path P and two nodes r and y , an Euler switch of P at nodes x , y yields an Euler path P containing exactly the same set of 2 ...
Page 312
... Euler path starting at node v , that is not v ̧ - optimal . If there is no v , -optimal Euler path that starts with the same edge that P does , then either there is a increasing Euler switch of P at some pair of nodes x and y , or there ...
... Euler path starting at node v , that is not v ̧ - optimal . If there is no v , -optimal Euler path that starts with the same edge that P does , then either there is a increasing Euler switch of P at some pair of nodes x and y , or there ...
Page 315
... Euler path . But 3 " choices suffice when the algorithm for 2 - optimal Euler paths is also employed . 6 Approximation Algorithms Now we consider Euler digraphs without any degree bounds , and present an algorithm that is guaranteed to ...
... Euler path . But 3 " choices suffice when the algorithm for 2 - optimal Euler paths is also employed . 6 Approximation Algorithms Now we consider Euler digraphs without any degree bounds , and present an algorithm that is guaranteed to ...
Contents
A Faster Algorithm for Approximate String Matching | 1 |
BoyerMoore Strategy to Efficient Approximate String Matching | 24 |
Computing Discoveries in Molecular Biology Abstract | 64 |
Copyright | |
16 other sections not shown
Other editions - View all
Common terms and phrases
2-paths alphabet approximate string matching approximation algorithm automaton binary bound characters combinatorial complexity Computer Science connected components consider construction contains corresponding cost CS-tree cycle cycle graph data structure defined degree-2 edit denote directed graph edges edit distance efficient error Euler path evolutionary trees exons filtration genes genome given hash functions hash table hinge input integer l-sets label lattice Lemma length ligand linear matching problem maximum independent set median tree method minimum mismatches models molecular molecule node NP-complete NP-hard O(log O(nm occurrences optimal pair partition pattern matching permutation phyloDAG phylogeny phylograph polynomial position prefix preprocessing Proof protein protein folding q-gram query random receptor represented s-block S-labelled trees sequence solution space species spliced alignment step subgraph substring subtree suffix tree superstring symbols synteny target template algorithm Theorem trie vertex vertices weight word suffix tree