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"”.

  1. 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. …

    nus Repository record for CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES (opens in a new tab) Download file for CHARACTERIZE WEAK AND SUPER STABILITY OF THE ROOMMATE PROBLEM UNDER WEAK PREFERENCES (opens in a new tab)

  2. 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 …

    calpoly Repository record for RFID Antenna Coverage Optimization (opens in a new tab)

  3. 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 …

    toronto-retro Repository record for Tree Spanners of Simple Graphs (opens in a new tab)

  4. 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 …

    nps Repository record for Project scheduling tool (opens in a new tab)

  5. 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 …

    baylor Repository record for Solving the F/A-18 mission computer virtual memory problem. (opens in a new tab)

  6. 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 …

    mississippi Repository record for Genetic Algorithm For University Course Timetabling Problem (opens in a new tab)

  7. 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 …

    nps Repository record for A branch-and-bound algorithm for the network diversion problem (opens in a new tab)

  8. 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 …

    lethbridge Repository record for Point cover problem in 3D (opens in a new tab)

  9. 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 …

    nus Repository record for Modelling and scheduling of heterogeneous computing systems (opens in a new tab) Download file for Modelling and scheduling of heterogeneous computing systems (opens in a new tab)

  10. 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 …

    rice Repository record for Reducing the impact of spill code (opens in a new tab)

  11. 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 …

    nps Repository record for Implementation of an efficient algorithm to detect maximal cliques in a conflict graph (opens in a new tab)

  12. 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 …

    brazil-ufrgs Repository record for A model-driven design-space exploration tool for the HIPAO 2 methodology (opens in a new tab)

  13. 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 …

    qucosa-diss

  14. 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 …

    nps Repository record for Approximating the chromatic number of an arbitrary graph using a supergraph heuristic (opens in a new tab)

  15. 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 …

    must-thes Repository record for The directed Steiner problem on graphs: A simulated annealing approach (opens in a new tab)

  16. 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)

    iu Repository record for Discrete Quantum Theories and Computing (opens in a new tab)

  17. 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 …

    iastate Repository record for Graph compression using heuristic-based reordering (opens in a new tab)

  18. 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 …

    arizona-thes Repository record for The system design process is intractable, but robust. (opens in a new tab)

  19. 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 …

    rice Repository record for New algorithms for pathwidth computation (opens in a new tab)

  20. 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 …

    maryland Repository record for Using Join Networks to Compute Satisfiability (opens in a new tab)

Page 1 of 5