Sökning: "NP-complete."

Visar resultat 1 - 5 av 20 avhandlingar innehållade ordet NP-complete..

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

    Författare :Martin Lagerholm; Beräkningsbiologi och biologisk fysik - Genomgår omorganisation; []
    Nyckelord :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;

    Sammanfattning : 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. LÄS MER

  3. 2. Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems

    Författare :Biman Roy; Peter Jonsson; Victor Lagerkvist; Arnaud Durand; Linköpings universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : 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. LÄS MER

  4. 3. Distributed connectivity algorithms

    Författare :Esther Jennings; Luleå tekniska universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Dependable Communication and Computation Systems; Kommunikations- och beräkningssystem;

    Sammanfattning : The goal of this research is to design efficient distributed algorithms which execute on an arbitrary network to recognize special connectivity structures within that network. In some cases, we also consider the maintenance of these special structures in dynamically changing networks. LÄS MER

  5. 4. On state space structure and average case complexity in random K-SAT problems

    Författare :John Ardelius; Erik Aurell; Bart Selman; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computer science; Datavetenskap;

    Sammanfattning : This thesis gives an introduction to a currently active area in the cross-section between theoretical computer science and theoretical physics. In the last ten years it has been suggested that critical behaviour, usually seen in models from condensed matter physics, may be responsible for the intractability of NP complete computation problems. LÄS MER

  7. 5. Strong Partial Clones and the Complexity of Constraint Satisfaction Problems : Limitations and Applications

    Författare :Victor Lagerkvist; Peter Jonsson; Christer Bäckström; Nadia Creignou; Linköpings universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES;

    Sammanfattning : In this thesis we study the worst-case time complexity of the constraint satisfaction problem parameterized by a constraint language (CSP(S)), which is the problem of determining whether a conjunctive formula over S has a model. To study the complexity of CSP(S) we borrow methods from universal algebra. LÄS MER