All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 11 Next

Displaying 201 – 220 of 532

Showing per page

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2004)

RAIRO - Operations Research - Recherche Opérationnelle

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2010)

RAIRO - Operations Research

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large....

Histoires de fichiers

Jean Françon (1978)

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

Hopcroft's algorithm and tree-like automata

G. Castiglione, A. Restivo, M. Sciortino (2011)

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

Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have...

Hopcroft's algorithm and tree-like automata

G. Castiglione, A. Restivo, M. Sciortino (2011)

RAIRO - Theoretical Informatics and Applications

Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have...

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,...

Incremental DFA minimisation

Marco Almeida, Nelma Moreira, Rogério Reis (2014)

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

We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.

Job shop scheduling with unit length tasks

Meike Akveld, Raphael Bernhard (2012)

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

In this paper, we consider a class of scheduling problems that are among the fundamental optimization problems in operations research. More specifically, we deal with a particular version called job shop scheduling with unit length tasks. Using the results of Hromkovič, Mömke, Steinhöfel, and Widmayer presented in their work Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms, we analyze the problem setting for 2 jobs with an unequal number of tasks. We contribute a deterministic algorithm...

Currently displaying 201 – 220 of 532