Editorial Cuvillier

Publicaciones, tesis doctorales, capacitaciónes para acceder a una cátedra de universidad & prospectos.
Su editorial internacional especializado en ciencias y economia

Editorial Cuvillier

De En Es
"Algorithmic and Computational Complexity Issues of MONET

Impresion
EUR 23,00 EUR 21,85

E-Book
EUR 0,00

Download
PDF (1,1 MB)
Open Access CC BY 4.0

"Algorithmic and Computational Complexity Issues of MONET (Tienda española)

Matthias Hagen (Autor)

Previo

Indice, Datei (48 KB)
Lectura de prueba, Datei (120 KB)

In this thesis, we study the problem Monet—the Mo(notone) n(ormal form)
e(quivalence) t(est)—that asks to decide equivalence of a monotone disjunctive normal form . and a monotone conjunctive normal form ψ. This problem is a covering problem that can be interpreted as the task of enumerating all (in some sense) minimal solutions of some system. Hence, there is a huge number of similar questions in many problems from diverse applications.Our results can roughly be divided into results on the design and evaluation of algorithms for Monet and results that rather touch complexity questions related to the problem. As for the algorithmic part, we will give lower bounds for several known algorithms and report results obtained by practically examining the theoretically
fastest algorithm in computational experiments. As for the complexity
part of this thesis, we show several restricted classes of the problem to be solvable in logarithmic space, which improves previously known polynomial time bounds. We also show Monet to be in the complexity class of .xed-arameter tractable problems with respect to several parameters. More precisely, we prove the following main results using various algorithmic and computational complexity techniques. – Several restricted classes of Monet are solvable in logarithmic space. In
particular, these are the classes where the DNF– contains only a constant number of monomials (Section 4.1.1), contains only monomials of constant size (Section 4.1.2), contains only monomials that each do not contain only a constant number of variables
(Section 4.1.3),- is regular (Section 4.2.1), aligned (Section 4.2.2), or 2-monotonic (Section 4.2.3).- The DL-algorithm (Section 5.1.2), the BMR-algorithm (Section 5.1.3), the KS-algorithm (Section 5.1.4), and the HBC-algorithm (Section 5.2) for the
problem Monet are not output-polynomial. Their running times are at
least nÙ(log log n), where n denotes the size of the input and output.-FK-algorithm B for the problem Monet is experimentally competitive to FK-algorithm A on many classes (Chapter 6).-Monet is .xed-parameter tractable with respect to the parameters
– number v of variables in . and ψ (Section 7.1),
– number m of monomials in . (Section 7.2),
– a parameter q describing the variable frequencies in . (Section 7.3),
– and a parameter bounding the unions of transversals or edges of .’s
associated hypergraph (Section 7.4.3).
This thesis contains material (to be) published in the journals Discrete Applied Mathematics, Information and Computation and Information Processing Letters, as well as material (to be) presented at, and (to be) published in the proceedings
of, the conference “Mathematical Foundations of Computer Science” (MFCS 2005), and the workshops “Graph-Theoretic Concepts in Computer Science” (WG 2007), “Parameterized and Exact Computation” (IWPEC 2008) and “Workshop on Algorithm Engineering & Experiments” (ALENEX 2009).

ISBN-10 (Impresion) 3867278261
ISBN-13 (Impresion) 9783867278263
ISBN-13 (E-Book) 9783736928268
Idioma Inglés
Numero de paginas 162
Edicion 1 Aufl.
Volumen 0
Lugar de publicacion Göttingen
Lugar de la disertacion Universität Jena
Fecha de publicacion 15.12.2008
Clasificacion simple Tesis doctoral
Area Matemática
Informática