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 26 for “"maximum cardinality"”.

  1. A Sparsification Based Algorithm for Maximum-Cardinality Bipartite Matching in Planar Graphs

    … the one of special interest to us being the Maximum Cardinality Bipartite Matching in Planar Graphs. In this work, we present a novel sparsification based approach for computing maximum/perfect bipartite matching in planar graphs. The overall complexity of our algorithm is O(n<sup>6/5</sup> …

    vt Repository record for A Sparsification Based Algorithm for Maximum-Cardinality Bipartite Matching in Planar Graphs (opens in a new tab)

  2. A Separator-Based Framework for Graph Matching Problems

    … particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimum-cost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, long-standing combinatorial …

    vt Repository record for A Separator-Based Framework for Graph Matching Problems (opens in a new tab)

  3. Complexity results and integer programming models for hospitals / residents problem variants

    … preference lists, it is possible to find a maximum cardinality stable matching or report that none exists in polynomial time. Since an instance of HRC need not admit a stable matching, it is natural to seek the ‘most stable’ matching possible, i.e., a matching that admits the minimum number …

    glasgow Download PDF for Complexity results and integer programming models for hospitals / residents problem variants (opens in a new tab)

  4. A primal-dual algorithm for the maximum charge problem with capacity constraints

    In this thesis, we study a variant of the maximum cardinality matching problem known as the maximum charge problem. Given a graph with arbitrary positive integer capacities assigned on every vertex and every edge, the goal is to maximize the assignment of positive feasible charges on the edges …

    lethbridge Repository record for A primal-dual algorithm for the maximum charge problem with capacity constraints (opens in a new tab)

  5. Approximating Properties of Data Streams

    … we consider the problem of estimating the maximum weighted matching of a graph whose edges are revealed in a streaming fashion. We develop a reduction from the maximum weighted matching problem to the maximum cardinality matching problem that only doubles the approximation factor of a …

    purdue-thes Repository record for Approximating Properties of Data Streams (opens in a new tab)

  6. Alliance Partitions in Graphs.

    … strong alliance partition number) is the maximum cardinality of a partition of V into defensive alliances (respectively, strong defensive alliances). The global (strong) alliance partition number is defined similarly. For each parameter we give both general bounds and exact values. Our …

    etsu Repository record for Alliance Partitions in Graphs. (opens in a new tab) Download PDF for Alliance Partitions in Graphs. (opens in a new tab)

  7. An Algorithm for Stable Matching with Approximation up to the Integrality Gap

    … preferences, computing a stable matching of maximum cardinality is known to be NP-hard. Furthermore, it is known to be NP-hard to achieve a performance guarantee of 33/29 − ε (≈ 1.1379) and UGC-hard to attain that of 4/3 − ε (≈ 1.3333). We present a polynomial-time approximation algorithm …

    waterloo Repository record for An Algorithm for Stable Matching with Approximation up to the Integrality Gap (opens in a new tab)

  8. Combinatorics of finite sets

    … then among the intersecting subfamilies of I of maximum cardinality there is a star. In Chapter 1, we prove Chvatal's conjecture for several special cases. Let I be an ideal in 2$\sp{\lbrack n\rbrack }$ that is compressed with respect to a given element. We prove that among the largest …

    uiuc Repository record for Combinatorics of finite sets (opens in a new tab)

  9. Bounds on the length of test sequences for conformance testing of communication protocols.

    … first type of efficient algorithms utilize the maximum-cardinality minimum-cost matching algorithm. The second type of efficient algorithms utilize the rural Chinese postman tour algorithm. Moreover, the sufficiency conditions for the second type of algorithms to find a minimum length test …

    ottawa-retro Repository record for Bounds on the length of test sequences for conformance testing of communication protocols. (opens in a new tab)

  10. Optimization of Online Advertising on Search Engines

    … the help of Metropolis-Hasting Algorithm and Maximum cardinality matching of bipartite graph.

    buffalo Repository record for Optimization of Online Advertising on Search Engines (opens in a new tab)

  11. New results on broadcast domination and multipacking

    … k from v. The multipacking number of G is the maximum cardinality of a multipacking of G. In the first part of the thesis, we describe how linear programming can be used to give a cubic algorithm to find the broadcast domination number and multipacking number of strongly chordal graphs. Next, …

    uvic Repository record for New results on broadcast domination and multipacking (opens in a new tab)

  12. Social Event Organization

    … function, while respecting the minimum and maximum cardinality bounds associated with events. The problem is shown to be NP-complete, and in fact, hard to approximate [24]. First, we review the previous solutions proposed in [24] and discuss some problems in these algorithms. Then, we …

    concordia Download PDF for Social Event Organization (opens in a new tab)

  13. Bounds on the cardinalities of nearly neighborly and neighborly families of polytopes

    … quadrilaterals and conjecture that this is the maximum. Using techniques developed by J. Zaks for nearly-neighborly tetrahedra, we show that a family of nearly neighborly quadrilaterals has at most 14 members. A family of nearly neighborly quadrilaterals is said to share a base line if all …

    uiuc Repository record for Bounds on the cardinalities of nearly neighborly and neighborly families of polytopes (opens in a new tab)

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

  15. An Approximation Algorithm for the Stable Marriagae Problem with Ties and Incomplete Lists

    … Here, we seek to find a stable matching of maximum cardinality. The problem was shown to be NP-hard, and is one of the most prominent problems in the domain of ordinal matching. When preference lists are restricted to one side of the problem, Iwama et al. [28] devised a variant of the famous …

    clemson Repository record for An Approximation Algorithm for the Stable Marriagae Problem with Ties and Incomplete Lists (opens in a new tab)

  16. Hypercube coloring and the structure of binary codes

    … binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square …

    ubc Repository record for Hypercube coloring and the structure of binary codes (opens in a new tab) Download PDF for Hypercube coloring and the structure of binary codes (opens in a new tab)

  17. Distributed Algorithms in Membrane Systems

    … find sets of edge- and node-disjoint paths of maximum cardinality in O(mn) steps. These solutions are the first P algorithms for solving the edge- and node-disjoint paths problems in membrane systems.

    auckland-ms Repository record for Distributed Algorithms in Membrane Systems (opens in a new tab)

  18. Algorithmic aspects of fixed-size coalition formation

    … a set of agents, the problem is to find a maximum-cardinality set of r-cliques in an undirected graph subject to that set being either vertex disjoint or edge disjoint, for a fixed integer r ≥ 3. This general problem is known as the Kr- packing problem. Here we study the restriction of this …

    glasgow Repository record for Algorithmic aspects of fixed-size coalition formation (opens in a new tab) Download PDF for Algorithmic aspects of fixed-size coalition formation (opens in a new tab)

  19. Integer linear programming techniques for constant dimension codes and related structures

    … of subspace coding are the determination of the cardinality of largest subspace codes and the classification of subspace codes. Using integer linear programming techniques and symmetry, this thesis answers partially the questions above while focusing on CDCs. With the coset construction and the …

    bayreuth Repository record for Integer linear programming techniques for constant dimension codes and related structures (opens in a new tab)

Page 1 of 2