# bipartite graph

(redirected from Bigraph)

## bipartite graph

[bī′pär‚tīt ′graf]
(mathematics)
A linear graph (network) in which the nodes can be partitioned into two groups G1 and G2 such that for every arc (i,j) node i is in G1 and node j in G2.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

## bipartite graph

References in periodicals archive ?
Actually, finding bipartitioning of bigraph can be understood as classifying each point into two classes, for example, +1 and -1.
A bigraph, the affinity graph, is used to model the affinity of user equivalents to sites, G(U, S) or G(U, F), which is undirected with vertex set V|S [union] U} or V[F [union] U} such that there is an edge between users u [member of] U and s [member of] S or f [member of] F if user u is under the coverage umbrella of site s or FAP f.
SPHier [7] extract clusters from dataset using bipartite crossing minimization biclustering techniques but instead of serial Bigraph crossing minimization using parallel algorithm in order to increase the performance of the algorithm beside the enhancement made on Cheng and Church biclustering algorithm to enable the local search for clusters instead of global search because after the Bigraph reordering the related values arranged together in blocks and global search is useless.
Following [3, 4, 24], by an edge-bipartite graph (bigraph, in short), we mean a pair [DELTA] = ([[DELTA].sub.0], [[DELTA].sub.1]), where [[DELTA].sub.0] is a finite nonempty set of vertices and [[DELTA].sub.1] is a finite set of edges equipped with a bipartition [[DELTA].sub.1] = [[DELTA].sup.-.sub.1] [union] [[DELTA].sup.+.sub.1] such that the set [[DELTA].sub.1](i,j) = [[DELTA].sup.-.sub.1](i, j) [union] [[DELTA].sup.+.sub.1](i, j) of edges connecting the vertices i and j does not contain edges lying in [[DELTA].sup.-.sub.1](i, j) [intersection] [[DELTA].sup.+.sub.1](i, j), for each pair of vertices i, j [member of] [[DELTA].sub.0], and either [[DELTA].sub.1](i, j) = [[DELTA].sup.-.sub.1](i, j) or [[DELTA].sub.1](i,j) = [[DELTA].sup.+.sub.1](i,j).
Since different process executions result from choices in a process model, we propose to preprocess the annotated CFP of each process model (Algorithm 2) as follows: first we transform such a CFP to a set of conflict-free CFPs (specified by function GetAllExecutions in Algorithms 3) and then convert each resulting CFP to a directed bipartite graph (or bigraph) (specified by AnnotatedCFP2Bigraph in Algorithm 5).
The bigraph associated with M is the undirected bipartite graph on vertices V = X [union] Y that has [x.sub.i] ~ [y.sub.j] if and only if [m.sub.ij] [not equal to] 0.
(2001) Heuristics, Experimental Subjects, and Treatment Evaluation in Bigraph Crossing Minimization.
[3] The bigraph ex when it appears initially may be written + instead of c+, as in extremely [+trimli], exit [+;t], x-ray [+-re], and EXTRA [\$TRA].
For odd k [member of] [Z.sup.+], the kth bipartite power [G.sup.[k]] of a bigraph G has the same vertex set as G, and two vertices are adjacent in [G.sup.[k]] if and only if their distance in G is at most k and odd.
Wang, "An algorithm for constructing the maximum matching graphs on bigraphs," Acta Electronica Sinica, vol 38, no.
Phonologic treatment for deep dyslexia using bigraphs instead of graphemes.

Site: Follow: Share:
Open / Close