Displaying similar documents to “Efficient validation and construction of border arrays and validation of string matching automata”

Computing and proving with pivots

Frédéric Meunier (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

A simple idea used in many combinatorial algorithms is the idea of . Originally, it comes from the method proposed by Gauss in the 19th century for solving systems of linear equations. This method had been extended in 1947 by Dantzig for the famous simplex algorithm used for solving linear programs. From since, a pivoting algorithm is a method exploring subsets of a ground set and going from one subset to a new one ′ by deleting an element inside and adding an element outside : ′ =  ...

Computing -Free NFA from Regular Expressions in ( log()) Time

Christian Hagenah, Anca Muscholl (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The standard procedure to transform a regular expression of size to an -free nondeterministic finite automaton yields automata with states and ( ) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic showed how to build an -free NFA with only ( log()) transitions. The current lower bound on the number of transitions is Ω( log()). A rough running time estimation for the common follow sets (CFS) construction proposed...

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the -metric traveling salesman problem ( -TSP), , the TSP restricted to graphs satisfying the -triangle inequality ({}) ≤ (({}) + ({})), for some cost function and any three vertices . The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3 /2 and is the best known algorithm for the -TSP, for 1 ≤  ≤ 2....