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 98 for “"NP-complete problem"”.
-
CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES
… the weak and super stability of the roommate problem under weak preferences and extends the no-odd ring condition of stable roommate matching established in \cite{chung2000existence}. We demonstrate that finding such a stable partition under weak stability conditions is an NP-complete problem. …
-
RFID Antenna Coverage Optimization
This research focuses on the problem of determining the location of RFID antennas required to read RFID tags from all items in a facility, such that the number of antennas is minimized. We formulate the problem as a Set Covering optimization problem. We develop a heuristic algorithm for this …
-
Tree Spanners of Simple Graphs
… whether a graph admits a tree t-spanner is an NP-complete problem. This thesis studies tree t-spanners from both theoretical and algorithmic perspectives. In particular, it is proved that a nontree graph admits a unique tree t-spanner for at most one value of stretch factor t. As a corollary, a …
-
Project scheduling tool
… of developers on a large software project is an NP- complete problem. The scheduling algorithm employed by the Evolutionary Control System (ECS) portion of the Computer-Aided Prototyping System (CAPS) does near-optimal scheduling using an algorithm that runs in Order N2 space and time. The …
-
Solving the F/A-18 mission computer virtual memory problem.
… by the system. Determining these addresses is an NP-Complete problem, to which the only known way of finding a solution is exponential-time search. We present a formalization and analysis of the problem, along with an analysis of the feasibility of performing search. Additionally, we explore a …
-
Genetic Algorithm For University Course Timetabling Problem
… and healthcare scheduling is a complex problem. It is difficult and time consuming to solve due to many constraints. Depending on whether the constraints are essential or desirable they are categorized as ‘hard’ and ‘soft’, respectively. Two types of timetables, namely, course and …
-
A branch-and-bound algorithm for the network diversion problem
In the network diversion problem (NDP), we must find a minimum-weight set of edges in a directed graph G = (V,E) whose deletion forces all s-t communication to pass through one or more diversion edges in a diversion set ED . We develop and test a specialized branch-and-bound algorithm for this …
-
Point cover problem in 3D
We examine the problem of covering points with minimum number of axis-parallel lines in three dimensional space which is an NP-complete problem. We introduce Lagrangian based algorithms to approximate the point cover problem. We study the Lift-and-Project relaxation of the standard IP to obtain …
-
Modelling and scheduling of heterogeneous computing systems
… allocation model was proposed. To solve this NP-complete problem, a Genetic Algorithm and Tabu Search were developed, the latter outperforming the former. Further improvements in performance were obtained by using a Parallel Tabu Search. To solve a completion time oriented task scheduling …
-
Reducing the impact of spill code
… heuristics to arrive at a "good" answer to the NP-complete problem of allocation, resulting in suboptimal code. We look at a post-pass to the allocator which removes unnecessary spill code by finding places where the availability of an unused register allows us to "promote" a spill to a …
-
Implementation of an efficient algorithm to detect maximal cliques in a conflict graph
… used to model radio communications networks. The problem considered is the detection of maximal cliques, representing subnets, from the 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 …
-
A model-driven design-space exploration tool for the HIPAO 2 methodology
… is being developed at UFRGS. Among the problems that designers must solve, the task-to-processor mapping in heterogeneous multiprocessor systems is an NP-complete problem and the design space will quickly become too large to be explored adequately by humans. This work details the …
-
Satisfiability and Optimization in Periodic Traffic Flow Problems
… in public railway transport systems is an NP-complete problem – namely the Periodic Event Scheduling Problem (PESP). The original model is restricted to basic periodic timetabling. Extending the model by decisional transport networks with flows induces new possibilities in the timetabling …
-
Approximating the chromatic number of an arbitrary graph using a supergraph heuristic
… the minimum number of colors is in general an NP-complete problem. However, there are several classes of graphs for which coloring is a polynomial-time problem. One such class is the chordal graphs. This thesis deals with an experimental algorithm to approximate the chromatic number of an input …
-
The directed Steiner problem on graphs: A simulated annealing approach
"The well-known Steiner Problem on Graphs is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. In this dissertation a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of …
-
Discrete Quantum Theories and Computing
… that it can be used to solve the UNIQUE-SAT problem, which is as hard as a general NP-complete problem. (See the thesis for full Abstract)
-
Graph compression using heuristic-based reordering
… to achievemaximal compression is a well known NP complete problem, the Optimal Linear Arrangement.</p> <p>Our work focuses on the inverted index format, where each node has its corresponding list ofneighbours. We propose a heuristic based graph reordering, using the property that the cost …
-
The system design process is intractable, but robust.
… is intractable because it is proven to be NP-complete. It is robust, because the tools used to do the system design are robust and allow for very good, but not optimal, solutions. The system design process is proven to be NP-complete by reduction of the Knapsack problem. The solutions used …
-
New algorithms for pathwidth computation
… but also in practice. Theoretically, lots of NP-hard problems become polynomially solvable when restricted in graphs with bounded pathwidth (or treewidth). Practically, pathwidth and treewidth have significant applications in many different fields such as searching games, VLSI design, matrix …
-
Using Join Networks to Compute Satisfiability
… of propositional logic formulas is a canonical NP-complete problem; algorithms for its solution have been studied for over forty years. The representational power of propositional logic allows a host of research and real-world problems to be solved using SAT solvers: some prominent areas of …
Page 1 of 5