China 
Africa 
Explore chapters and articles related to this topic
Introduction to graph theory
Published in Karthik Raman, An Introduction to Computational Systems Biology, 2021
A bipartite graph is a special type of graph, where there are two disjoint independent3 sets of nodes, such that no two nodes within the same set have edges between them. Bipartite graphs arise naturally in scenarios where there are two types of objects (e.g. flights and airports, or actors and movies), or two sets of people (e.g. men and women). Film actor networks are bipartite, where the two sets of nodes represent actors and movies, and edges connect actors to the movies they starred in. Bipartite graphs are two-colourable, in that every node can be assigned a colour such that no two adjacent nodes in the entire graph have the same colour. It is also helpful to think of this in terms of shapes—a graph of squares and ellipses, where no ellipse is adjacent to another ellipse, and no square is connected to another square (as we will see in Figure 2.10). Bipartite graphs are also very useful to represent a wide range of biological networks, capturing diverse kinds of information, ranging from disease–gene networks or drug–target networks (§4.2), to metabolic networks (§2.5.5). It is possible to make projections of bipartite graphs, to compress the information. Naturally, two different projections are possible, for each node type (colour/shape)—the edges in the projection connect every pair of nodes that were separated by two edges in the bipartite graph. We will discuss examples in §4.4.2.
Introduction
Published in Vlad P. Shmerko, Svetlana N. Yanushkevich, Sergey Edward Lyshevski, Computer Arithmetics for Nanoelectronics, 2018
Vlad P. Shmerko, Svetlana N. Yanushkevich, Sergey Edward Lyshevski
A bipartite graph is one whose vertices can be partitioned into two (disjoint) nonempty sets, S1 and S2, in such a way that every edge joints with a vertex in S1 and a vertex in S2. A complete bipartite graph is a bipartite graph in which every vertex in S1 is joined to every vertex in S2.
Understanding Crossbar Switch Fabrics
Published in James Aweya, Switch/Router Architectures, 2019
By casting the problem as an equivalent network flow problem [TARJANR83], one can find the maximum size matching for a bipartite graph. A maximum matching algorithm is an algorithm that finds a match (in the equivalent bipartite graph) with the maximum size (algorithm called maxsize), or weight (maxweight). The maxweight algorithm reduces to maxsize if the weight assigned to each of the edges (lines) in the bigraph is equal to unity. Maximum size matching is also referred to as maximum cardinality matching or, simply, maximum bipartite matching.
Integration of ridesharing and activity travel pattern generation
Published in Transportmetrica A: Transport Science, 2023
Ali Najmi, Travis Waller, Wei Liu, Taha H. Rashidi
We represent the driver-passenger interactions as a bipartite graph G, such that each tuple of participants and the corresponding link are represented by two nodes of (, ) and (, ). The nodes are classified into two major sets of drivers-ridesharing links and passengers-ridesharing links to be used in the bipartite graph matching problem. In bipartite graphs, nodes are divided into two disjoint sets, in which only the link between two nodes in different sets is permitted (Blattner, Zhang, and Maslov 2007; Guillaume and Latapy 2006). However, the problem at hand is to some extent different. In our problem, each of the major sets is partitioned into and minor groups, respectively, where at most one link from/to each group is permitted. Therefore, we provide a generalised version of bipartite graph matching problem in which the partitioned groups are incorporated.
Automated digital cause-and-effect diagrams to assist causal analysis in problem-solving: a data-driven approach
Published in International Journal of Production Research, 2020
In the current manufacturing industry, quality management in general and quality problem-solving (QPS) in particular play essential roles in fulfilling the expectations of demanding customers who seek high-quality (but low-cost) products. QPS refers to processes related to problem definition, problem analysis, cause identification, solution generation and selection, and solution-testing and evaluation (MacDuffie 1997). The data recorded and stored during QPS usually include problems, causes, temporary solutions, long-term solutions, and solution evaluations (Xu, Dang, and Munro 2018). If the problems and causes within the QPS data are considered vertices, then their counterparts in the original records and the connections between them will constitute a bipartite graph. A bipartite graph is a ubiquitous data structure that simulates relationships between two entity types, and examples include users and projects, and queries and web pages (He et al. 2016). In a bipartite graph consisting of the original problem record and the cause record, one problem record is often connected to one or more cause records, and one cause record relates to only one problem record; therefore, a bipartite graph does not reflect complex cause-and-effect relationships, such as one-cause and multieffects, or multicauses and multieffects (Rehder 2010). In a bipartite graph, problem vertices described differently may essentially represent the same or a similar problem; similarly, different cause vertices may involve the same cause. To cluster the two ends of the bipartite graph and obtain the associations between classes, many scholars have proposed methods by which to partition and cluster bipartite graphs (Liu, Shang, and Chen 2009; Gaume, Navarro, and Prade 2013; Xu et al. 2016; El-Kilany, Tazi, and Ezzat 2017). If the two ends of a bipartite graph (consisting of the original problem record and the cause record) were to be clustered separately, the same or similar problems/causes will be brought together; from this, a new bipartite graph consisting of the problem class and the cause class would be formed. Based on this new graph, we could obtain the complex relationship between the problem and the cause, such as one-cause and multieffects, or multicauses and multieffects. However, when there are large numbers of problem classes and cause classes, a bipartite graph is too large to display intuitively.