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"”.
-
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> …
-
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 …
-
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 …
-
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 …
-
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 …
-
Weight Annealing Heuristics for Solving Bin Packing and other Combinatorial Optimization Problems: Concepts, Algorithms and Computational Results
… item orientation constraints. We also solve the maximum cardinality bin packing problem and the multidimensional multiple knapsack problem with our heuristics.
-
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 …
-
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 …
-
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 …
-
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 …
-
Optimization of Online Advertising on Search Engines
… the help of Metropolis-Hasting Algorithm and Maximum cardinality matching of bipartite graph.
-
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, …
-
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 …
-
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 …
-
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 …
-
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 …
-
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 …
-
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.
-
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 …
-
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 …
Page 1 of 2