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 71 for “"NP Completeness"”.

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

  2. An alternative proof for the NP-completeness of the Grid Subgraph problem

    … σχάρας. Αποδεικνύουμε ότι το πρόβλημα αυτό είναι NP-πλήρες χρησιμοποιώντας απλά και διαισθητικά για να ανάγουμε σε αυτό μία παραλλαγή του προβλήματος SAT (ικανοποίησης λογικής φόρμουλας). Προς αυτό αποδεικνύουμε ότι και η ειδική περίπτωση του προβλήματος στην οποία το μέγεθος της σχάρας είναι …

    athens Repository record for An alternative proof for the NP-completeness of the Grid Subgraph problem (opens in a new tab)

  3. Efficient Computations of Interesting Paths

    … For the k-IP problem, we show its preceding NP-completeness proof has gaps. We give a new NP-completeness proof of the k-IP problem for k ≥ 4. We design approximation and exact algorithms for it. For the IP problem, we give a proof of its NP-completeness. We also design corresponding …

    carleton Repository record for Efficient Computations of Interesting Paths (opens in a new tab)

  4. Complexity and algorithms related to two classes of graph problems

    … the size of a minimum conversion set is NP-hard. We show that the AND-OR model defines a convexity on graphs. We show results of NP-completeness and efficient algorithms for certain convexity parameters for this new one, as well as approximate algorithms. We introduce the concept of …

    brazil-uerj Repository record for Complexity and algorithms related to two classes of graph problems (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. Limited broadcast domination

    … parameters. In Chapter 3, we give a proof of NP-completeness for the problem of determining the k-limited broadcast domination number for a fixed graph G, as well as a proof of NP-completeness for its dual problem of determining the k-limited multipacking number. Chapter 4 focuses on cubic and …

    uvic Repository record for Limited broadcast domination (opens in a new tab)

  7. Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών

    … we present polynomial-time algorithms or NP-completeness results for various types of the coloring problem on graphs and polynomial-time algorithms for the longest path problem on perfect graphs. In particular, motivated by the de nition of linear coloring on simplicial complexes, recently …

    greece Repository record for Χαρακτηρισμός νέων κλάσεων τέλειων γραφημάτων και αγλόριθμοι χρωματισμού και μέγιστων διαδρομών (opens in a new tab)

  8. Reconstructing hv-convex polyominoes with multiple colours

    … that is O(Cmin(n^{2C}, m^{2C})nm), and an NP-completeness proof when the number of colours is unbounded.

    waterloo Repository record for Reconstructing hv-convex polyominoes with multiple colours (opens in a new tab)

  9. Minimal PMU placement for graph observability: a decomposition approach

    … such that the entire graph is observed. The NP-completeness of PMU placement for planar bipartite graphs is shown. PMU placement algorithms are developed for graphs of bounded tree width, such as trees and outer planar graphs. Graph decompositions are used to develop efficient algorithms that …

    vt Repository record for Minimal PMU placement for graph observability: a decomposition approach (opens in a new tab)

  10. Some results on symmetric signings

    … with specific spectral properties. We show NP-completeness for verifying whether an arbitrary matrix has a symmetric signing that is positive semi-definite, is singular, or has bounded eigenvalues. We exhibit a stark contrast between invertibility and the above-mentioned spectral properties …

    uiuc Repository record for Some results on symmetric signings (opens in a new tab)

  11. Fundamentals and applications of order dependencies

    … of order dependency classes; (iii) a proof of co-NP-completeness of the inference problem for ODs and for the subclass of UODs; (iv) a proof of co-NP-completeness of the inference problem of functional dependencies (FDs) from ODs in general, but demonstrate linear time complexity for the inference …

    york Repository record for Fundamentals and applications of order dependencies (opens in a new tab)

  12. On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs

    … a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, where at each round, an informed vertex can send the message to at most one of its uninformed neighbors. We study the problem in cactus graphs and graphs of bounded pathwidth. Despite …

    york Repository record for On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs (opens in a new tab)

  13. Analysis of bin packing variants

    … In this thesis, we first demonstrate the NP-completeness of Bin Packing via a reduction from Three-Dimensional Matching, establishing its foundational complexity. We then survey core heuristics for the one-dimensional case and extend our analysis to two and three-dimensional variants, …

    unf Repository record for Analysis of bin packing variants (opens in a new tab) Download PDF for Analysis of bin packing variants (opens in a new tab)

  14. Problems in Sorting and Graph Algorithms

    … conjecture that every sorting algorithm on some input involves every key in O(log n) comparisons. We give partial results. The third problem concerns finding efficient algorithms for finding cycles of small fixed length in graphs. We give algorithms for general graphs and O(n log n) algorithms for …

    uiuc Repository record for Problems in Sorting and Graph Algorithms (opens in a new tab)

  15. Instruction and data cache modeling for timing analysis in real-time systems

    … case performance, but they are a source of unpredictability, especially in the worst case software timing analysis with the consideration of data caches. This is a critical problem in real-time systems, where tight Worst Case Execution Time (WCET) is required for their schedulability …

    nus Repository record for Instruction and data cache modeling for timing analysis in real-time systems (opens in a new tab) Download file for Instruction and data cache modeling for timing analysis in real-time systems (opens in a new tab)

  16. Using motif databases to help improve multiple sequence alignment

    … of the unknown sequences. However, due to the NP-completeness nature of the multiple sequence alignment, exhaustive searching method is unrealistic. Current algorithms use heuristic approach to get a nearly global optimal result. As a consequence, any specific program may encounter certain …

    concordia Download PDF for Using motif databases to help improve multiple sequence alignment (opens in a new tab)

  17. Square Root Finding In Graphs

    … of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with …

    brock Repository record for Square Root Finding In Graphs (opens in a new tab)

Page 1 of 4