The search session has expired. Please query the service again.
Displaying 201 –
220 of
532
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...
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....
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...
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...
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,...
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.
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