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 14 of 14 for “"minimum vertex cover"”.

  1. On approximating transitivity and tractability of graphs

    … the problems of finding the largest clique, minimum colouring, maximum independent set and minimum vertex cover are NP-hard. But, there exists some families of graphs, called perfect graphs, where these problems become tractable. One particular class of perfect graphs are the the underlying …

    colostate Repository record for On approximating transitivity and tractability of graphs (opens in a new tab)

  2. On Barrier Graphs of Sensor Networks

    … which captures information about the network's coverage. Every such ray-barrier sensor network corresponds to a barrier graph, but not every graph is the barrier graph of some network. We show that any barrier graph is not just tripartite, but perfect. We describe how to find networks which have …

    denver Repository record for On Barrier Graphs of Sensor Networks (opens in a new tab)

  3. Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs

    … support measures that brings together existing minimum-image-based and overlap-graph-based support measures. Our framework is built on the concept of occurrence / instance hypergraphs. Based on that, we present two new support measures: minimum instance (MI) measure and minimum vertex cover …

    usf Repository record for Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs (opens in a new tab)

  4. Diversity optimization and parameterized analysis of heuristic search methods for combinatorial optimization problems

    … combinatorial optimization problem, namely minimum vertex cover problem, to a local search algorithm and compare its performance with the core component of the state-of-the-art algorithm. After that, we investigate how well-performing local search algorithms for small or medium size …

    adelaide Repository record for Diversity optimization and parameterized analysis of heuristic search methods for combinatorial optimization problems (opens in a new tab)

  5. Modern Large-Scale Algorithms for Classical Graph Problems

    … matching, maximal independent set, minimum vertex cover, and graph connectivity in these models that substantially improve upon the state-of-the-art and are in many cases optimal. Many of our algorithms build on model-independent tools and ideas that are of independent interest and …

    maryland Repository record for Modern Large-Scale Algorithms for Classical Graph Problems (opens in a new tab)

  6. Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation

    … in the streaming setting. We study approximate minimum cut, k-vertex connectivity, maximum matching, minimum vertex cover, and correlation clustering across different streaming models—including insertion-only, dynamic, and random-order streams. By establishing tight upper and lower bounds—often …

    waterloo Repository record for Optimal Graph Streaming Algorithms and Further Advances in Modern Models of Computation (opens in a new tab)

  7. Applications of Entanglement in Quantum Information

    … the output states are nonorthogonal, we use minimum-error and unambiguous state discrimination to show that entangled initial states and collective measurements confer an advantage when detectors are grouped, and we develop a shift-operator formalism that gives closed-form success …

    cuny-grad Repository record for Applications of Entanglement in Quantum Information (opens in a new tab)

  8. Streaming Maximum Matching in a Few Passes: Algorithms and Lower Bounds

    … model and give an α-approximation algorithm for minimum vertex cover using O(n^2/α^2) space, matching the space lower bound by Dark and Konrad [CCC’20] up to constant factors.

    bristol Repository record for Streaming Maximum Matching in a Few Passes: Algorithms and Lower Bounds (opens in a new tab) Download PDF for Streaming Maximum Matching in a Few Passes: Algorithms and Lower Bounds (opens in a new tab)

  9. Formalizing Combinatorial Matrix Theory

    … size $e \times f$ such that $e\leq f$, where the minimum cover is of size $e$, our procedure computes a maximum selection of size $e$, row by row.</p> <p>Furthermore, we show that Menger's Theorem, Hall's Theorem, and Dilworth's Theorem---theorems related to $\KMM$---can also be proven feasibly; …

    mcmaster Repository record for Formalizing Combinatorial Matrix Theory (opens in a new tab)

  10. Rhizomatic Cognitive Computing Continuum

    … learning model that formulates deployment as a minimum vertex cover problem, reducing resource usage and latency. Finally, the SLA violation prediction layer employs composite GNN architectures that synthesize temporal, topological, and semantic information to enable accurate early warnings of …

    greece Repository record for Rhizomatic Cognitive Computing Continuum (opens in a new tab)

  11. Resilient and Risk-Averse Network Systems

    … grounded in coherent risk measures to identify minimum-risk graph structures under stochastic vertex and/or edge weights. First, we consider a network flow problem and propose an approach for developing resilience metrics, where resilience refers to the network’s capability to restore optimal or …

    arizona-thes Repository record for Resilient and Risk-Averse Network Systems (opens in a new tab)

  12. Flexible integration of classical and quantum techniques in the evolutionary path to quantum utility

    … of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial …

    uvic Repository record for Flexible integration of classical and quantum techniques in the evolutionary path to quantum utility (opens in a new tab)

  13. Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations

    … n/ log log n)) LS+ relaxation of the Vertex Cover polytope has integrality gap 2-epsilon. The integrality gap of the standard SDP for Vertex Cover remains 2-o(1) even if all hypermetric inequalities are added to the relaxation. The resulting relaxations are incomparable to the SDP …

    toronto-retro Repository record for Integrality Gaps for Strong Linear Programming and Semidefinite Programming Relaxations (opens in a new tab)