Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 85 for “"NP-complete problems"”.
-
Learning to solve NP-complete problems
… decision variant of the TSP, a highly relevant NP-Complete problem. Our model is trained to function as an effective message-passing algorithm in graph in which edges from the input graph communicate with vertices from the input graph for a number of iterations after which the model is asked to …
-
Clustering solutions: a novel approach to solving NP-complete problems
… we introduce a novel approach to solving MAX-SAT problems. This algorithm clusters good solutions, and restarts the search from the closest feasible configuration to the centroid of each cluster. We call this method Clustered-Landscape Guided Hopping (CLGH). In addition, where clustering does not …
-
The INDEPENDENT SET Decision Problem is NP-complete
… the theory of computational complexity. Some problems seemed hard-to-compute, while others were easy. It turned out that many of the hard problems were equally hard in a way that could be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was …
-
Computational Complexity of Soundness Verification for Neural Networks
… systems. Neural networks trained to solve NP-complete problems, in particular, are unlikely to be able to solve the problem exactly. However, a weaker soundness guarantee may be sufficient for some systems, e.g., that positive instances of the problem may be rejected but no negative …
-
Visualization of Ant Pheromone Based Path Following
… as a demonstration of a heuristic approach to NP-complete problems and as an educational tool for demonstrating how ant colonies gather food. An interactive real time 3D visualization is built on top of the simulation. A graphical user interface layer allows user interaction with the simulation …
-
An Interactive Tutorial for NP-Completeness
… Complexity Theory, reductions, and the NP-Complete class of problems are considered difficult by students. Numerous algorithm visualizations (AVs) have been developed over the years to portray the dynamic nature of known algorithms commonly taught in undergraduate classes. However, to …
-
Hamiltono ciklo ieškojimas kvantiniais skaičiavimais /
… search problem is one of the most well-known problems in graph theory, and is relevant in many areas such as computer graphics, network routing, and many others. The Hamiltonian cycle problem belongs to the class of NP-complete problems, so that in the general case the solution of the problem …
-
Topics in Graph Algorithms: Structural Results and Algorithmic Techniques, with Applications
… the design of polynomial time algorithms for NP-complete problems in a way that guarantees some, often worst-case, satisfactory performance when compared to exact (optimal) solutions. We mainly study some emergent techniques that help to bridge the gap between computational intractability and …
-
Branch decompositions and their applications
Many real-life problems can be modeled as optimization or decision problems on graphs. Also, many of those real-life problems are NP-hard. One traditional method to solve these problems is by branch and bound while another method is by graph decompositions. In the 1980's, Robertson and Seymour …
-
Structure and randomness in complex networks applied to the target set selection problem : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Manawatu, New Zealand
… complex networks to efficiently solve difficult NP-complete problems, with the aim of obtaining better or faster solutions than would be possible for general graphs. Two related NP-complete problems are selected for study: the minimum target set problem, and the maximum activation set problem. …
-
Automatic data layout for distributed memory machines
… In the proposed framework, instances of NP-complete problems are solved during the construction of candidate layout search spaces and the final selection of candidate layouts from each search space. Rather than resorting to heuristics prematurely, the framework capitalizes on …
-
Dual-Based Local Search for Deterministic, Stochastic and Robust Variants of the Connected Facility Location Problem
… propose the study of a family of network design problems that arise in a wide range of practical settings ranging from telecommunications to data management. We investigate the use of heuristic search procedures coupled with lower bounding mechanisms to obtain high quality solutions for …
-
Hybrid solvers for the Boolean Satisfiability problem: an exploration
… (SAT) is one of the most extensively researched NP-complete problems in Computer Science. This thesis focuses on the design of feasible solvers for this problem. A SAT problem instance is a formula in propositional logic. A SAT solver attempts to find a solution for the formula. Our research …
-
Developing effcient simulators for cell machines
… are suitable to tackle relevant real-life problems, usually involving NP-complete problems. Moreover, P systems are excellent tools to investigate on the computational complexity boundaries, in particular tackling the P versus NP problem. In this way, by studying how the ingredients …
-
Improved Approximation Algorithms for Geometric Packing Problems With Experimental Evaluation
Geometric packing problems are NP-complete problems that arise in VLSI design. In this thesis, we present two novel algorithms using dynamic programming to compute exactly the maximum number of k x k squares of unit size that can be packed without overlap into a given n x m grid. The first …
-
Implementation of an efficient algorithm to detect maximal cliques in a conflict graph
… graph model. However, detection of cliques is an NP-complete problem. Since NP-complete problems are not likely to be solvable in a reasonable time if the input is large, this paper limits the network input to six stations and fifteen transmissions. An algorithm is implemented in Pascal to detect …
-
Characterizing neighborhoods favorable to local search techniques
NP-Complete problems are the most difficult problems to solve and polynomial time algorithms to solve these problems do not exist. One of the more powerful approaches for such problems are heuristic direct search techniques. For a given problem, a landscape is composed of (1) a solution space, (2) …
-
Euristiniai algoritmai NP-pilniems uždaviniams spręsti ir jų realizacija GRIDui /
… algorithms for GRID computing network to solve NP-complete problems. The problems of NP-complete set are not solved in polynomial time. To solve such problems, researchers have to use heuristic algorithms. Heuristic algorithms always give result in polynomial time, but it doesn’t mean that …
-
An investigation into the structure of Chinese remainder representation
… For a long time a number of CRR related problems have been recognized as being hard to implement efficiently. The lack of an efficient implementation for some of these problems has meant that CRR has only been able to be used to implement hardware solutions for very specific problems. The …
-
Relaxing synchronization in distributed simulated annealing
… the solution to combinatorial optimization problems. Since simulated annealing is a general purpose method, it can be applied to the broad range of NP-complete problems such as the traveling salesman problem, graph theory, and cell placement with a careful control of the cooling schedule. …
Page 1 of 5