Page 1

Displaying 1 – 14 of 14

Showing per page

Implementation of directed acyclic word graph

Miroslav Balík (2002)

Kybernetika

An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text T is a minimal automaton that accepts all substrings of a text T , so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i. e. vertices,...

Improved Lower Bounds on the Approximability of the Traveling Salesman Problem

Hans-Joachim Böckenhauer, Sebastian Seibert (2010)

RAIRO - Theoretical Informatics and Applications

This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless 𝒫 = 𝒩𝒫 ). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, Delta-TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively,...

Inductive computations on graphs defined by clique-width expressions

Frédérique Carrère (2009)

RAIRO - Theoretical Informatics and Applications

Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function D, if G is a graph with n vertices and of clique-width at most k, where k is fixed, we can associate with each vertex x of G a piece of information (bit sequence) lab(x) of length O(log2(n)) such that we can compute D in constant time, using only the labels...

Influence of modeling structure in probabilistic sequential decision problems

Florent Teichteil-Königsbuch, Patrick Fabiani (2006)

RAIRO - Operations Research

Markov Decision Processes (MDPs) are a classical framework for stochastic sequential decision problems, based on an enumerated state space representation. More compact and structured representations have been proposed: factorization techniques use state variables representations, while decomposition techniques are based on a partition of the state space into sub-regions and take advantage of the resulting structure of the state transition graph. We use a family of probabilistic exploration-like...

Currently displaying 1 – 14 of 14

Page 1