Background: A matching between two sets A and B assigns some elements of A to some elements of B. Finding the similarity between two sets of elements by advantage of the matching is widely used in computational biology for example in the contexts of genome-wide and sequencing association studies. Frequently, the capacities of the elements are limited. That is, the number of the elements that can be matched to each element should not exceed a given number. Results: We use bipartite graphs to model relationships between pairs of objects. Given an undirected bipartite graph G = (A [ B;E), the b-matching of G matches each vertex v in A (resp. B) to at least 1 and at most b(v) vertices in B (resp. A), where b(v) denotes the capacity of v. We propose the rst O(n3) time algorithm for nding the maximum weight b-matching of G, where jAj + jBj = O(n).

Conclusions: The b-matching has been studied widely for the bipartite graphs with integer weight edges. But our algorithm is the rst algorithm for the maximum (respectively minimum) b-matching problem with non positive real (respectively non negative real) edge weights.

Figure 1

Figure 2

This preprint is available for download as a PDF.

This is a list of supplementary files associated with this preprint. Click to download.

- extraplaceins.sty
- figure1.png
- graphicx.sty
- landscap.sty
- natbib.sty
- stfloats.sty
- url.sty
- color.sty
- bmcart.cls
- bmcarticle.bib
- crop.sty
- algorithm.sty
- algorithmic.sty
- figure2.png
- bmcmathphys.bst
- bmcarticle.tex
- float.sty
- spbasic.bst
- alltt.sty
- array.sty
- algpascal.sty
- algorithmicx.sty
- etoolbox.sty
- ReferencePDF.pdf
- algorithm2e.sty
- chngpage.sty
- caption.sty
- vancouver.bst
- bmcartbiblio.sty
- flushend.sty
- algpseudocode.sty

Loading...

Posted 26 Mar, 2020

###### No community comments so far

Posted 26 Mar, 2020

###### No community comments so far

Background: A matching between two sets A and B assigns some elements of A to some elements of B. Finding the similarity between two sets of elements by advantage of the matching is widely used in computational biology for example in the contexts of genome-wide and sequencing association studies. Frequently, the capacities of the elements are limited. That is, the number of the elements that can be matched to each element should not exceed a given number. Results: We use bipartite graphs to model relationships between pairs of objects. Given an undirected bipartite graph G = (A [ B;E), the b-matching of G matches each vertex v in A (resp. B) to at least 1 and at most b(v) vertices in B (resp. A), where b(v) denotes the capacity of v. We propose the rst O(n3) time algorithm for nding the maximum weight b-matching of G, where jAj + jBj = O(n).

Conclusions: The b-matching has been studied widely for the bipartite graphs with integer weight edges. But our algorithm is the rst algorithm for the maximum (respectively minimum) b-matching problem with non positive real (respectively non negative real) edge weights.

Figure 1

Figure 2

This preprint is available for download as a PDF.

This is a list of supplementary files associated with this preprint. Click to download.

- extraplaceins.sty
- figure1.png
- graphicx.sty
- landscap.sty
- natbib.sty
- stfloats.sty
- url.sty
- color.sty
- bmcart.cls
- bmcarticle.bib
- crop.sty
- algorithm.sty
- algorithmic.sty
- figure2.png
- bmcmathphys.bst
- bmcarticle.tex
- float.sty
- spbasic.bst
- alltt.sty
- array.sty
- algpascal.sty
- algorithmicx.sty
- etoolbox.sty
- ReferencePDF.pdf
- algorithm2e.sty
- chngpage.sty
- caption.sty
- vancouver.bst
- bmcartbiblio.sty
- flushend.sty
- algpseudocode.sty

Loading...