Search for dissertations about: "NP-complete problem"

Showing result 1 - 5 of 17 swedish dissertations containing the words NP-complete problem.

2. 1. Resource Allocation with Potts Mean Field Neural Network Techniques

   Author : Martin Lagerholm; Beräkningsbiologi och biologisk fysik - Genomgår omorganisation; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Potts; combinatorial optimization; ANN; mean field; approximation; routing; unicast; multicast; airline crew; scheduling; ECG; NP-complete.; Matematik; Mathematics; algorithm; Systems engineering; computer technology; Data- och systemvetenskap; Fysicumarkivet A:1998:Lagerholm;

   Abstract : Potts mean field artificial neural network techniques are developed and applied to airline crew scheduling problems and routing problems. A propagator formalism in terms of Potts neurons is developed to handle global topological issues. An integrated method for identifying and classifying ECG complexes is presented. READ MORE

4. 2. Complexity Dichotomies for CSP-related Problems

   Author : Gustav Nordh; Peter Jonsson; Andrei Krokhin; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Complexity; Constraint Satisfaction Problem; System of Equations; Nonmonotonic Logic; Circumscription; Abduction; Isomorphism; Computer science; Datavetenskap;

   Abstract : Ladner’s theorem states that if P ≠ NP, then there are problems in NP that are neither in P nor NP-complete. Csp(Γ) is a class of problems containing many well-studied combinatorial problems in NP. READ MORE

5. 3. Order-preserving graph grammars

   Author : Petter Ericson; Henrik Björklund; Frank Drewes; Sebastian Maneth; Umeå universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Graph grammars; graph parsing; graph series; hyperedge replacement; uniform parsing problem; abstract meaning representation; semantic modelling; order preservation; reentrancy preservation; minimally adequate teacher; weighted graph grammars;

   Abstract : The field of semantic modelling concerns formal models for semantics, that is, formal structures for the computational and algorithmic processing of meaning. This thesis concerns formal graph languages motivated by this field. READ MORE

6. 4. Constructing Evolutionary Trees - Algorithms and Complexity

   Author : Anna Östlin; Institutionen för datavetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Computer science; Maximum homeomorphic subtrees; Consensus trees; Experiment model; Evolutionary trees; Complexity; Computational biology; Algorithms; Data structures; numerical analysis; systems; control; Datalogi; numerisk analys; system; kontroll; Biology; Biologi;

   Abstract : In this thesis three general problems concerning construction of evolutionary trees are considered. Algorithms for the problems are presented and the complexity of the problems is investigated. The thesis consists of three corresponding parts. The first part is devoted to the problem of constructing evolutionary trees in the experiment model. READ MORE

7. 5. Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems

   Author : Biman Roy; Peter Jonsson; Victor Lagerkvist; Arnaud Durand; Linköpings universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES;

   Abstract : In this thesis we study the worst-case complexity ofconstraint satisfaction problems and some of its variants. We use methods from universal algebra: in particular, algebras of total functions and partial functions that are respectively known as clones and strong partial clones. READ MORE