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 2 Next

Displaying 21 – 40 of 47

Showing per page

Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

Xiaoguang Yang (2010)

RAIRO - Operations Research

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Computing complexity distances between algorithms

Salvador Romaguera, Enrique A. Sánchez-Pérez, Oscar Valero (2003)

Kybernetika

We introduce a new (extended) quasi-metric on the so-called dual p-complexity space, which is suitable to give a quantitative measure of the improvement in complexity obtained when a complexity function is replaced by a more efficient complexity function on all inputs, and show that this distance function has the advantage of possessing rich topological and quasi-metric properties. In particular, its induced topology is Hausdorff and completely regular. Our approach is applied to the measurement...

Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time

Christian Hagenah, Anca Muscholl (2010)

RAIRO - Theoretical Informatics and Applications

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

Currently displaying 21 – 40 of 47