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