China
Africa
Explore chapters and articles related to this topic
Transshipment problems
Published in V. K. Balakrishnan, Network Optimization, 2019
The relation between matchings and coverings is not immediately apparent. Suppose M is an arbitrary matching consisting of k edges. Then M will be joining 2k distinct vertices pairwise. So any covering should have at least k vertices. Thus the cardinality of a matching cannot exceed the cardinality of a covering and consequently the size of a maximum matching is always less than or equal to the size of a minimum covering in a graph. In the case of a bipartite graph the surprising fact is that these two numbers are equal, as shown in Theorem 2.8.
Spanning Trees
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
The maximum-matching problem is to find a matching in a weighted graph, whose total edge-weight is a maximum. The hereditary subset system that corresponds to this maximum-weight problem is (EG, I), where I is the set of matchings in the graph G.
Modeling and Simulation Tools for Mobile Ad Hoc Networks
Published in Jonathan Loo, Jaime Lloret Mauri, Jesús Hamilton Ortiz, Mobile Ad Hoc Networks, 2016
Kayhan Erciyes, Orhan Dagdeviren, Deniz Cokuslu, Onur Yılmaz, Hasan Gumus
A matching in a graph G is a set of nonloop edges with no shared endpoints. The vertices incident to the edges of a matching M are saturated by M. A maximal matching is a set of edges that cannot be extended by adding an extra edge. A perfect or maximum matching in a graph is a matching that saturates every vertex [6]. Maximum matching problem is in the P complexity set. An example matching, maximal matching, and perfect matching are shown with bold edges in Figure 3.12a, b, and c, respectively.
Decentralised fixed modes of networked MIMO systems
Published in International Journal of Control, 2018
Yuqing Hao, Zhisheng Duan, Guanrong Chen
In a directed graph, an edge (i, j) is directed from i to j, where i is the tail and j is the head of the edge. For node system i, define the sets of its in-neighbours and out-neighbours as Nini = {j ∈ {1, …, N}|βij ≠ 0} and Nouti = {j ∈ {1, …, N}|βji ≠ 0}, respectively. The in-degree and the out-degree of node i are the cardinalities of Nini and Nouti, respectively. A matching is a set of edges that do not share any common tail or common head. A maximum matching is a matching that contains the largest possible number of edges in the graph. A node is called a matched node if it is the head of an edge in a matching, otherwise it is an unmatched node. A perfect matching is a matching which matches all nodes in the graph, which is a certainly a maximum matching. A graph formed by a sequence of edges {(vi, vi + 1)|i = 1, 2,… , l − 1} with no repeated nodes is called a path, denoted as v1,… , vl, where v1 is the beginning and vl is the end of the path, and vl is said to be reachable from v1. If v1,… , vl is a path, then the graph formed by adding the edge (vl, v1) is a cycle. A graph without circles is called a tree. The node in a tree which can reach every other node is called the root of the tree. A leaf in a rooted tree is a node of degree 1 that is not the root. A chain is a tree with only one leaf.
Optimal strategies for the lifeline differential game with limited lifetime
Published in International Journal of Control, 2021
Rui Yan, Zongying Shi, Yisheng Zhong
Then, a bipartite graph can be generated with pursuers and evaders as two sets of nodes. Edges will be drawn from each pursuer to all the evaders that it can win against. Then any algorithm for maximum bipartite matching can be applied to find a maximum matching solution, as described in Chen et al. (2017). An example of five pursuers and four evaders is depicted in Figure 8.
Sparktope: linear programs from algorithms
Published in Optimization Methods and Software, 2022
The matching problem and its relationship to the field of extension complexity was one of the main motivations of our work. A matching M in an undirected graph with n vertices is a set of vertex disjoint edges from E. The maximum matching problem is to find a matching in G with the largest number of edges. A related decision problem is to decide if a given matching M in G has maximum size. Both of these problems can be solved in polynomial time by running Edmonds' algorithm [8]. As well as this combinatorial algorithm, Edmonds also introduced a related polytope [7] which is known as the Edmonds' polytope and whose variables correspond the edges of the complete graph . Matching problems can be solved by a linear program with constraint set , where the coefficients of the objective function are one for the edge set E and zero otherwise. Unlike his algorithm's polynomial running time, has size exponential in n. This raised the question of whether could be the projection of a higher dimensional polytope that does have polynomial size. Such a polytope is called an extended formulation and is the central concept in extension complexity (see, e.g. Fiorini et al. [9]). However, in a celebrated result, Rothvoss [14] proved admits no polynomial size extended formulation. Rothvoss's result has sometimes been misinterpreted to mean that no polynomial sized LP exists for the matching problem. In Section 6 of the paper, we give details of the construction of a uniform family of LPs for the maximum matching problem that have polynomial size.