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 583 for “"NP-complete"”.

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

    brazil-ufrgs Repository record for Learning to solve NP-complete problems (opens in a new tab)

  2. The INDEPENDENT SET Decision Problem is NP-complete

    … be precisely specified. They became known as the NP-complete problems. The SATISFIABILITY problem (SAT) was the first problem to be proved NP-complete in 1971. Since then numerous other hard-to-solve problems have been proved to be in NP-complete. In this paper we will examine the problem of how …

    vcu Repository record for The INDEPENDENT SET Decision Problem is NP-complete (opens in a new tab)

  3. Clustering solutions: a novel approach to solving NP-complete problems

    In this thesis, 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 …

    soton Download PDF for Clustering solutions: a novel approach to solving NP-complete problems (opens in a new tab)

  4. On the Complexity of Scheduling University Courses

    … courses is hard, even as hard as solving an NP-Complete problem. There are many papers in the literature that make this assertion but rarely are precise problem definitions provided and no papers were found which offered proofs that the university course scheduling problem being discussed is …

    calpoly Repository record for On the Complexity of Scheduling University Courses (opens in a new tab)

  5. On the complexity of energy-efficient broadcasting in wireless networks

    … networks. Some versions are known to be NP-complete. We show that the Euclidean version with unlimited power levels is also NP-complete. We assume a broadcast power metric of p(r) = kra where r is the broadcast radius, and k > 0 and a > 2 are properties of the signal propagation medium. …

    uvic Repository record for On the complexity of energy-efficient broadcasting in wireless networks (opens in a new tab)

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

  7. Rearranjo de genomas : algoritmos e complexidade

    … diameter. We develop approximation algorithms, NP-completeness and properties about these problems. Regarding the sorting by transpositions, which is an NP-complete problem, several approximation algorithms were proposed based on the graph called the reality and desire diagram. Through a case …

    brazil-uerj Repository record for Rearranjo de genomas : algoritmos e complexidade (opens in a new tab)

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

    vt Repository record for An Interactive Tutorial for NP-Completeness (opens in a new tab)

  9. Complexity of Minimum Corridor Guarding Problems

    … by the guard. These problems are proved to be NP-complete. Keywords: computational complexity, computational geometry, corridor guarding, NP-complete"

    cuny Repository record for Complexity of Minimum Corridor Guarding Problems (opens in a new tab)

  10. Discovering Domain Orders through Order Dependencies

    … towards the most general case, which we prove is NP-complete. We then consider discovering approximate implicit orders; i.e., those that exist with some exceptions. We propose definitions of approximate implicit orders and prove that all non-trivial cases are NP-complete. We show that the …

    waterloo Repository record for Discovering Domain Orders through Order Dependencies (opens in a new tab)

  11. Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks

    The Hamilton cycle decision problem is NP-complete. No polynomial time algorithm that solves this problem is known, and may or may not exist. In this thesis, the co-NP complete non-Hamilton cycle decision problem is investigated via the heuristic O(n^8) weak closure algorithm, with modifications …

    guelph Repository record for Investigating the Use of Perfecting Matching in an Algorithm to Detect Non-Hamiltonicity of Snarks (opens in a new tab)

  12. Branch decompositions and their applications

    … 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 conceived of two new ways to decompose the graph in order to solve these problems. …

    rice Repository record for Branch decompositions and their applications (opens in a new tab)

  13. Search-based Optimization for Compiler Machine-code Generation

    … encompasses many steps. Parsing turns the input program into a more manageable syntax tree. Verification ensures that the program makes some semblance of sense. Finally, code generation transforms the internal abstract program representation into an executable program. Compilers strive to …

    oregon Repository record for Search-based Optimization for Compiler Machine-code Generation (opens in a new tab)

  14. The computational complexity of edge colouring restricted graphs

    … determining the chnmatic index is, in general, NP­-complete. This thesis investigates the computational complexity of edge colouring restricted graphs. Previous work has established that the chromatic index problem restricted to k­-regular graphs for any fixed k-3 remains NP-complete, whereas …

    uvic Repository record for The computational complexity of edge colouring restricted graphs (opens in a new tab)

  15. Directed acyclic constrained connectivity: complexity and applications

    … Directed Acyclic Constrained Connectivity is NP-Complete. We reduce Graph Coloring problems such as the 3-Coloring Problem to Directed Acyclic Constrained Connectivity. We also show that Directed Acyclic Constrained Connectivity can be related to the enumeration of Maximal Independent Sets. …

    colostate Repository record for Directed acyclic constrained connectivity: complexity and applications (opens in a new tab)

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

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

  17. Structural Properties of NP-Hard Sets and Uniform Characterisations of Complexity Classes

    … most important complexity classes are the class NP and the subclass of NP-complete problems, which comprises many important optimisation problems in the field of operations research. Moreover, with the P-NP-problem, the class NP represents the most important unsolved question in computer science. …

    wurz-thes Repository record for Structural Properties of NP-Hard Sets and Uniform Characterisations of Complexity Classes (opens in a new tab)

  18. On (in)tractability of connection and cut problems

    … its strict variant (S-TCP), when some of the input parameters are fixed, and they are restricted to specific graph classes, such as split graphs, rooted directed path graphs, and graphs of bounded clique-width. We mainly concentrate on results that differentiate the complexity of TCP from the …

    brazil-uerj Repository record for On (in)tractability of connection and cut problems (opens in a new tab)

  19. Semantic Order Compatibilities and Their Discovery

    … a semantic order relationship between columns is NP-complete, with some tractable special cases. We give an algorithm to automatically discover semantic order relationships in the data, we provide examples of interesting orders found by our algorithm that were missed by existing algorithms, and we …

    waterloo Repository record for Semantic Order Compatibilities and Their Discovery (opens in a new tab)

Page 1 of 30