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

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

    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)

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

    freiburg-diss Repository record for Fundamental algorithmic techniques for distributed computations in networks : information dissemination and maximum matching (opens in a new tab)

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

    waterloo Repository record for Bounds on Maximum Matchings in 1-Planar Graphs (opens in a new tab)

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

    oxford Repository record for Some problems related to the Karp-Sipser algorithm on random graphs (opens in a new tab)

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

    bristol Repository record for On the Streaming and Communication Complexity for Interval and Graph Problems (opens in a new tab) Download PDF for On the Streaming and Communication Complexity for Interval and Graph Problems (opens in a new tab)

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

    south-carolina Repository record for A Hierarchical Framework for Phylogenetic and Ancestral Genome Reconstruction on Whole Genome Data (opens in a new tab)

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

    odu Repository record for Indifference Graphs and the Single Row Routing Problem (opens in a new tab)

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

    penn Repository record for Analyzing Massive Graphs in the Semi-streaming Model (opens in a new tab)

  9. 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.

    duquesne Repository record for A Chinese Version of an Authorship Attribution Analysis Program (opens in a new tab)

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

    maryland Repository record for Memory-Restricted and Secure Algorithms For Large Datasets (opens in a new tab)

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

    carleton Repository record for Matchings in Geometric Graphs (opens in a new tab)

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

    waterloo Repository record for Efficient Algorithms for RDV graphs (opens in a new tab)

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

    milano Repository record for CORRUGATED FEED-HORN ARRAYS FOR FUTURE CMB POLARIZATION EXPERIMENTS. (opens in a new tab)

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

    iastate Repository record for State encoding for low power (opens in a new tab)

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

    vcu Repository record for KE Theory & the Number of Vertices Belonging to All Maximum Independent Sets in a Graph (opens in a new tab)

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

    glasgow Download PDF for Efficient algorithms for optimal matching problems under preferences (opens in a new tab)

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

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

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

    ottawa-retro Repository record for Two distributed algorithms for finding matchings on a graph. (opens in a new tab)

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

    gatech Repository record for Allocation problems with partial information (opens in a new tab)

Page 1 of 2