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 39 for “"maximum matching"”.
-
Streaming Maximum Matching in a Few Passes: Algorithms and Lower Bounds
We study the approximate maximum bipartite matching problem in the insertion-only streaming model. The simple (1/2 = 0.5)-approximate Greedy maximal matching algorithm is the best-known one-pass algorithm using O(n polylog n) (semi-streaming) space where n is the number of vertices in the graph. …
-
Fundamental algorithmic techniques for distributed computations in networks : information dissemination and maximum matching
… graph problems; information dissemination and maximum matching, and provide algorithmic techniques and lower bound analyses in the CONGEST model of computation. In that, time is assumed to be synchronously slotted into consecutive rounds such that in each round, every processing unit performs …
-
Bounds on Maximum Matchings in 1-Planar Graphs
In this thesis, we study lower bounds on maximum matchings in 1-planar graphs. We expand upon the tools used for proofs of matching bounds in other classes of graphs as well as some original ideas in order to find these bounds. The first novel results we provide are lower bounds on maximum …
-
Some problems related to the Karp-Sipser algorithm on random graphs
… a greedy algorithm which aims to obtain a near-maximum matching on a given graph. The algorithm evolves through a sequence of steps. In each step, it picks an edge according to a certain rule, adds it to the matching and removes it from the remaining graph. The algorithm stops when the remining …
-
On the Streaming and Communication Complexity for Interval and Graph Problems
We study the Interval Selection and Maximum Matching problems in the streaming and one-way<br/>communication complexity settings.<br/>In the Interval Selection problem we are given a set of intervals, and asked for a largest pair<br/>wise non-overlapping subset. Previous work gave tight results for …
-
A Hierarchical Framework for Phylogenetic and Ancestral Genome Reconstruction on Whole Genome Data
… method (FARM) within the framework of maximum likelihood and weighted maximum matching. We designed binary code based framework to reconstruct evolutionary history for whole genome gene orders. We developed algorithms to estimate/predict missing adjacencies in ancestral reconstruction …
-
Indifference Graphs and the Single Row Routing Problem
… algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties which allow the solution of the other problems in linear time. Indifference graphs are further …
-
Analyzing Massive Graphs in the Semi-streaming Model
… distance spanners and approximating the maximum matching. In this thesis, we present some algorithms and techniques for (i) solving more complex problems in the semi-streaming model, (for example, problems in the dynamic model) and (ii) having better solutions for the problems which have …
-
A Chinese Version of an Authorship Attribution Analysis Program
… novels. We found that Character or forward maximum matching (FMM)-segmented words in conjunction with the K-Nearest Neighbor calculated using nominal KS worked best in our test.
-
Memory-Restricted and Secure Algorithms For Large Datasets
… fundamental problems in computer science such as maximum matching, sorting, edit distance and longest common subsequence in massive datasets. We consider two popular models to deal with massive inputs. The first model is the streaming model in which the input is represented as a sequence of items …
-
Matchings in Geometric Graphs
… edge set contains straight-line segments. A matching in a graph is a subset of edges of the graph with no shared vertices. A matching is called perfect if it matches all the vertices of the underling graph. A geometric matching is a matching in a geometric graph. In this thesis, we study …
-
Efficient Algorithms for RDV graphs
In this thesis, we study the maximum matching and minimum dominating set problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. A straightforward implementation of these algorithms would require $O(n+m)$ time. We improve their efficiency by …
-
CORRUGATED FEED-HORN ARRAYS FOR FUTURE CMB POLARIZATION EXPERIMENTS.
… (<-30 dB) reflection over a 20% bandwidth with a maximum matching of -40 dB at 105 GHz for all seven antennas. Beam pattern measurements indicate good repeatability and a low (-30 dB) sidelobe levels. This work is particularly relevant for future Cosmic Microwave Background polarisation …
-
State encoding for low power
… to introduce skew and then an area measure based maximum matching technique is applied to keep the area down. The use of non-minimal length encoding to further reduce power is investigated. The results indicate that non-minimal length encoding is good for power reduction in most cases. They also …
-
KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph
… $G$, let $\alpha (G)$ be the cardinality of a maximum independent set, let $\mu (G)$ be the cardinality of a maximum matching and let $\xi (G)$ be the number of vertices belonging to all maximum independent sets. Boros, Golumbic and Levit showed that in connected graphs where the independence …
-
Efficient algorithms for optimal matching problems under preferences
… this thesis we consider efficient algorithms for matching problems involving preferences, i.e., problems where agents may be required to list other agents that they find acceptable in order of preference. In particular we mainly study the Stable Marriage problem (SM), the Hospitals / Residents …
-
Formalizing Combinatorial Matrix Theory
… 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; in fact, all these theorems are equivalent to KMM, and …
-
Two distributed algorithms for finding matchings on a graph.
Two new distributed algorithms for finding matchings on a graph are presented. The first algorithm generates a spanning matching. A spanning matching on a graph is one with respect to which no two adjacent nodes are both free. Starting from any matching, the second algorithm proceeds in phases …
-
Allocation problems with partial information
… Concretely, we consider the online bipartite matching problem in the unknown distribution model and present the first algorithm that breaches the 1-1/e barrier for this problem. Next we study issues arising from data acquisition costs that are prevalent in ad-systems and kidney exchanges. …
Page 1 of 2