A Compendium of Applications of the

Graph Matching Problem

 


Figure 1. Landscape of matching problems. The vertex-weighted matching problem can be formulated as an edge-weighted matching problem. The weighted matching algorithms utilize techniques developed for the cardinality matching problem. The arrows indicate these relationships.

Application Areas

1.       Numerical scientific computing

2.       Multilevel graph algorithms (partitioning and clustering)

3.       Bioinformatics: Protein structure comparisons

4.       Image processing

5.       Mobile computing

6.       Scheduling in input-queued high-performance switches

7.       Operations Research

8.       Miscellaneous

 

QUICK SUMMARY OF APPLICATIONS

Legend:  B = Bipartite graphs; G = General graphs;

E = Exact algorithm; A = Approximation algorithm. 

 

1. Applications of Maximum (Edge) Weighted Matching:

Objective: Maximize the sum of the weights of the matched edges.

 

#

Description

Examples:

Type

1

Numerical Linear Algebra: (pivoting in Gaussian elimination; scaling)

Olschowka and Neumaier; Duff and Koster;

B,E

2

Scheduling in high-performance network switches and routers

McKweon

B, A/E

3

Rigidity percolation

Ref: www.pa.msu.edu/~duxbury/CSC2007.pdf

Duxbury, Hendrickson 1992

G, E?

4

Image Feature Matching (Stereo Matching)

Yong-Quing Cheng, et al., 1996; Fielding, et al., 1997

B, E, A

5

Protein Structure Comparisons

Taylor, WR, et al., 2002; Wang Y., et al., 2004

 

6

Multi-level algorithms (partitioning and clustering)

Karypis and Kumar; Hendrickson; Preis.

G, A

7

Paired Kidney Donation Program

Segev and Gentry

G, E

 

2. Maximum (Cardinality) Matching:

Objective: Maximize the number of edges in the matching.

#

Description

Examples:

Type

1

Numerical Linear Algebra: (block triangular form; Zero-free diagonals)

Duff and Reid; Pothen and Fan;

B,E


3. Maximum (Vertex) Weighted Matching:

Objective: Maximize the sum of the weights of the matched vertices.

 

#

Description

Reference:

Type

1

Scheduling in high-performance network switches and routers

Tabatabaee, et al.;

B, E

2

Sparsest basis problem

Pinar, Chow and Pothen;

B, E/A

Bibliography

 

 

·         M. Olschowka and A. Neumaier, A new pivoting strategy for Gaussian elimination, Linear Algebra Its Appl.240, 131 (1996).

 

·         Duff, I. S. and Koster, J. 1999. The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices. SIAM J. Matrix Anal. Appl. 20, 4 (Jul. 1999), 889-901.

 

·         Pothen, A. and Fan, C. 1990. Computing the block triangular form of a sparse matrix. ACM Trans. Math. Softw. 16, 4 (Dec. 1990), 303-324.

 

·         Duff, I. S. and Koster, J. 2000. On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix. SIAM J. Matrix Anal. Appl. 22, 4 (Jul. 2000), 973-996.

 

·         Duff, I. S. and Pralet, S. 2005. Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems. SIAM J. Matrix Anal. Appl. 27, 2 (Jun. 2005), 313-340.

 

·         Gupta, A. 2002. Recent advances in direct methods for solving unsymmetric sparse systems of linear equations. ACM Trans. Math. Softw. 28, 3 (Sep. 2002), 301-324.

 

·         Broman, D., Nyström, K., and Fritzson, P. 2006. Determining over- and under-constrained systems of equations using structural constraint delta. In Proceedings of the 5th international Conference on Generative Programming and Component Engineering (Portland, Oregon, USA, October 22 - 26, 2006). GPCE '06. ACM, New York, NY, 151-160.

 

·         Duff, I. S. and Reid, J. K. 1978. Algorithm 529: Permutations to Block Triangular Form [F1]. ACM Trans. Math. Softw. 4, 2 (Jun. 1978), 189-192.

 

·         Duff, I. S. 1981. Algorithm 575: Permutations for a Zero-Free Diagonal [F1]. ACM Trans. Math. Softw. 7, 3 (Sep. 1981), 387-390.

 

·         Duff, I. S. 1981. On Algorithms for Obtaining a Maximum Transversal. ACM Trans. Math. Softw. 7, 3 (Sep. 1981), 315-330.

 

·         Duff, I. S. and Reid, J. K. 1978. An Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix. ACM Trans. Math. Softw. 4, 2 (Jun. 1978), 137-147.

 

·         P. Bunus and P. Fritzson, Methods for Structural Analysis and Debugging of Modelica Models, 2nd International Modelica Conference, Proceedings, pp. 157-165. 2002.

 

·         Schenk, O., Wächter, A., and Hagemann, M. 2007. Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Comput. Optim. Appl. 36, 2-3 (Apr. 2007), 321-341.

 

·         Benzi, M. 2002. Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 2 (Nov. 2002), 418-477.

 

·         Grigori, L. and Li, X. S. 2002. A new scheduling algorithm for parallel sparse LU factorization with static pivoting. In Proceedings of the 2002 ACM/IEEE Conference on Supercomputing (Baltimore, Maryland). Conference on High Performance Networking and Computing. IEEE Computer Society Press, Los Alamitos, CA, 1-18.

 

·         Coleman, T. F. and Pothen, A. 1984 The Sparse Null Space Basis Problem. Technical Report. UMI Order Number: TR84-598., Cornell University.

 

·         Coleman, T. F. and Pothen, A. 1986 The Null Space Problem Ii: Algorithms. Technical Report. UMI Order Number: TR86-747., Cornell University.

 

·         Ali Pinar, Edmond Chow, and Alex Pothen, Combinatorial Algorithms for Computing Column Space Bases That Have Sparse Inverses, Electronic Transactions on Numerical Analysis, 22 (2006), pp. 122-145.

 

 

·         Karypis, G. and Kumar, V. 1996. Parallel multilevel k-way partitioning scheme for irregular graphs. In Proceedings of the 1996 ACM/IEEE Conference on Supercomputing (Cdrom) (Pittsburgh, Pennsylvania, United States, January 01 - 01, 1996). Conference on High Performance Networking and Computing. IEEE Computer Society, Washington, DC, 35.

 

·         G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. Technical Report TR 95-064, Department of Computer Science, University of Minnesota, 1995.

 

·         Karen Devine Erikg, Karen D. Devine, Erikg. Boman, Robert T. Heaphy, Rob H. Bisseling, Umit V. Catalyurek. Parallel Hypergraph Partitioning for Scientific Computing. In Proc. IPDPS’06. IEEE.

 

·         Gupta, A. 1997. Fast and effective algorithms for graph partitioning and sparse-matrix ordering. IBM J. Res. Dev. 41, 1-2 (Jan. 1997), 171-183.

 

·         Oliveira S., and Seok S. C, Multilevel approaches for large scale proteomic networks, International Journal of Computer Mathematics, 84(5) (2007), pp. 683-695.

 

·         Harvey, N. J., Ladner, R. E., Lovász, L., and Tamir, T. 2006. Semi-matchings for bipartite graphs and load balancing. J. Algorithms 59, 1 (Apr. 2006), 53-78.

 

·         Low, C. P. 2006. An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs. Inf. Process. Lett. 100, 4 (Nov. 2006), 154-161.

 

 

·         Petrova, D. and Stoichev, S. 2007. Protein structure similarity detection using alignment of secondary structure elements and their geometric properties. In Proceedings of the 2007 international Conference on Computer Systems and Technologies (Bulgaria, June 14 - 15, 2007). B. Rachev, A. Smrikarov, and D. Dimov, Eds. CompSysTech '07, vol. 285. ACM, New York, NY, 1-6.

 

·         Wang, Y., Makedon, F., Ford, J. A Bipartite Graph Matching Framework for Finding Correspondences between Structural Elements in Two Proteins. In Proceedings of the 26th Annual International Conference of the IEEE Engineering in Medicine and Biology Society, pages 2972--2975, San Francisco, California, 2004.

 

·         Taylor, WR. (2002) Protein Structure Comparison Using Bipartite Graph Matching and Its Application to Protein Structure Classification. Molecular and Cellular Proteomics 1, 334—339.

 

·         Markus Bauer and Gunnar W. Klau,Structural Alignment of Two RNA Sequences with Lagrangian Relaxation, Lecture Notes in Computer Science, Springer Berlin/Heidelberg. Volume 3341, 2005, Pages 113-123.

 

·         Haijun Liu, Dong Xu, Jianlin Shao, Yifei Wang, An RNA folding algorithm including pseudoknots based on dynamic weighted matching, Computational Biology and Chemistry, Volume 30, Issue 1, February 2006, Pages 72-76.

 

·         Deogun, J. S., Donis, R., Komina, O., and Ma, F. 2004. RNA secondary structure prediction with simple pseudoknots. In Proceedings of the Second Conference on Asia-Pacific Bioinformatics - Volume 29 (Dunedin, New Zealand). Y. P. Chen, Ed. ACM International Conference Proceeding Series, vol. 55. Australian Computer Society, Darlinghurst, Australia, 239-246.

 

·         Witwer, C., Hofacker, I. L., and Stadler, P. F. 2004. Prediction of Consensus RNA Secondary Structures Including Pseudoknots. IEEE/ACM Trans. Comput. Biol. Bioinformatics 1, 2 (Apr. 2004), 66-77.

 

·         Berger, B., Singh, R., and Xu, J. 2008. Graph algorithms for biological systems analysis. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, January 20 - 22, 2008). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 142-151.

 

·         Caprara, A. and Lancia, G. 2002. Structural alignment of large—size proteins via lagrangian relaxation. In Proceedings of the Sixth Annual international Conference on Computational Biology (Washington, DC, USA, April 18 - 21, 2002). G. Myers, S. Hannenhalli, D. Sankoff, S. Istrail, P. Pevzner, and M. Waterman, Eds. RECOMB '02. ACM, New York, NY, 100-108.

 

·         Lin, G., Wan, X., Tegos, T., and Li, Y. 2006. Statistical evaluation of NMR backbone resonance assignment. Int. J. Bioinformatics Res. Appl. 2, 2 (May. 2006), 147-160.

 

·         Langmead, C. J. and Donald, B. R. 2004. High-Throughput 3D Structural Homology Detection via NMR Resonance Assignment. In Proceedings of the 2004 IEEE Computational Systems Bioinformatics Conference (August 16 - 19, 2004). CSB. IEEE Computer Society, Washington, DC, 278-289.

 

·         Orhan Camoglu, Tamer Kahveci and Ambuj K. Singh. PSI: indexing protein structures for fast similarity search. Bioinformatics Vol. 19 Suppl. 1 2003. Pages i81-i83.

 

 

·         Wu, M. and Leou, J. 1995. A bipartite matching approach to feature correspondence in stereo vision. Pattern Recogn. Lett. 16, 1 (Jan. 1995), 23-31.

 

·         Paul M. Griffin, Correspondence of 2-D projections by bipartite matching, Pattern Recognition Letters, Volume 9, Issue 5, June 1989, Pages 361-366.

 

·         Yong-Qing Cheng, Victor Wu, Robert T. Collins, Allen R. Hanson, Edward M. Riseman. Maximum-Weight Bipartite Matching Technique and Its Application in Image Feature Matching. In Proc. SPIE Visual Comm. and Image Processing, 1996.

 

·         G Fielding & M Kam, Applying the hungarian method to stereo matching, 36th IEEE Conf. Decision & Control, ch.991, 1997, pp.1928-1933.

 

·         Gabriel Fielding, Moshe Kam, Weighted matchings for dense stereo correspondence, Pattern Recognition, Volume 33, Issue 9, September 2000, Pages 1511-1524.

 

·         Liatsis, P., Goulermas, J. Y., and Wang, Y. 2008. Stereo correspondence using symbiotic genetic algorithms. In Proceedings of the 9th WSEAS international Conference on Mathematics & Computers in Business and Economics (Bucharest, Romania, June 24 - 26, 2008). L. Vladareanu, V. Chiroiu, P. Bratu, and I. Magheti, Eds. World Scientific and Engineering Academy and Society (WSEAS), Stevens Point, Wisconsin, 97-104.

 

·         C. Stauffer and W. E. L. Grimson. Learning patterns of activity using real-time tracking. IEEE Transaction on Pattern Analysis and Machine Intelligence, 22(8):747-757, 2000. (http://www.anc.ed.ac.uk/demos/tracker/)

 

·         Scott, C.; Nowak, R., "Robust contour matching via the order-preserving assignment problem," Image Processing, IEEE Transactions on , vol.15, no.7, pp.1831-1838, July 2006.

 

·         Jun Xie, Pheng-Ann Heng, Mubarak Shah, Shape matching and modeling using skeletal context, Pattern Recognition, Volume 41, Issue 5, May 2008, Pages 1756-1767.

 

·         Grundmann, M.; Meier, F.; Essa, I., "3D Shape Context and Distance Transform for action recognition," Pattern Recognition, 2008. ICPR 2008. 19th International Conference on , vol., no., pp.1-4, 8-11 Dec. 2008.

 

 

·         Ferro A., Pigola G., Pulvirenti A., and Shasha D. Fast Clustering and Minimum Weight Matching Algorithms for Very Large Mobile Backbone Wireless Networks. Int. J. Found. Comput. Sci., volume 14, number 2, 2003, pages 223-236.

 

·         Gupta, I. 2001. Minimal CDMA Recoding Strategies in Power-Controlled Ad-Hoc Wireless Networks. In Proceedings of the 15th international Parallel &Amp; Distributed Processing Symposium (April 23 - 27, 2001). IEEE Computer Society, Washington, DC, 187.

 

·         Xing, G., Lu, C., Zhang, Y., Huang, Q., and Pless, R. 2007. Minimum power configuration for wireless communication in sensor networks. ACM Trans. Sen. Netw. 3, 2 (Jun. 2007).

 

 

·         N. McKeown, A. Mekkittikul, V. Anantharam and J. Walrand, Achieving 100% throughput in an input-queued switch, IEEE Trans. Commun. 47 (8) (1999), pp. 1260–1267.

 

·         McKeown, N. W. 1995 Scheduling Algorithms for Input-Queued Cell Switches. Doctoral Thesis. UMI Order Number: UMI Order No. GAX96-02658., University of California at Berkeley.

 

·         McKeown, N. 1999. The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM Trans. Netw. 7, 2 (Apr. 1999), 188-201.

 

·         Anderson, T. E., Owicki, S. S., Saxe, J. B., and Thacker, C. P. 1993. High-speed switch scheduling for local-area networks. ACM Trans. Comput. Syst. 11, 4 (Nov. 1993), 319-352.

 

·         Tamir, Y. and Chi, H. C. 1993. Symmetric Crossbar Arbiters for VLSI Communication Switches. IEEE Trans. Parallel Distrib. Syst. 4, 1 (Jan. 1993), 13-27.

 

·         Mekkittikul, A. 1999 Scheduling Nonuniform Traffic in High Speed Packet Switches and Routers. Doctoral Thesis. UMI Order Number: AAI9924465., Stanford University.

 

·         Momčilović, P. 2007. A distributed switch scheduling algorithm. Perform. Eval. 64, 9-12 (Oct. 2007), 1053-1061.

 

·         S. Deb, D. Shah and S. Shakkottai, Fast matching algorithms for repetitive optimization: An application to switch scheduling, Proc. CISS, Princeton, NJ (2006).

 

·         S. Sarkar, K. Kar, Achieving 2/3 throughput approximations with sequential maximal scheduling under primary interference constraints, in: Proc. Allerton Conference, Monticello, IL, 2006.

 

·         Bauer, C. 2005. Approximations to Maximum Weight Matching Scheduling Algorithms of Low Complexity. In Proceedings of the Advanced industrial Conference on Telecommunications/Service Assurance with Partial and intermittent Resources Conference/E-Learning on Telecommunications Workshop (July 17 - 22, 2005). AICT-SAPIR-ELETE. IEEE Computer Society, Washington, DC, 300-305.

 

·         Bauer, C. 2006. Low complexity, stable scheduling algorithms for networks of input queued switches with no or very low speed-up. SIGCOMM Comput. Commun. Rev. 36, 3 (Jul. 2006), 15-26.

 

·         Sanghavi, S., Bui, L., and Srikant, R. 2007. Distributed link scheduling with constant overhead. In Proceedings of the 2007 ACM SIGMETRICS international Conference on Measurement and Modeling of Computer Systems (San Diego, California, USA, June 12 - 16, 2007). SIGMETRICS '07. ACM, New York, NY, 313-324.

 

·         Marsan, M. A., Bianco, A., Giaccone, P., Leonardi, E., and Neri, F. 2002. Packet-mode scheduling in input-queued cell-based switches. IEEE/ACM Trans. Netw. 10, 5 (Oct. 2002), 666-678.

 

·         Fayyazi, M., Kaeli, D., and Meleis, W. 2006. An adjustable linear time parallel algorithm for maximum weight bipartite matching. Inf. Process. Lett. 97, 5 (Mar. 2006), 186-190.

 

·         Zhu, W. and Song, M. 2006. Integration of unicast and multicast scheduling in input-queued packet switches. Comput. Netw. 50, 5 (Apr. 2006), 667-687.

 

·         J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, pp. 556-564.

 

·         A. Baranowska and W. Kabaciński, The New Packet Scheduling Algorithms for VOQ Switches, Telecommunications and Networking - ICT 2004, 711-716.

 

·         Tabatabaee, V., Georgiadis, L., and Tassiulas, L. 2001. QoS provisioning and tracking fluid policies in input queueing switches. IEEE/ACM Trans. Netw. 9, 5 (Oct. 2001), 605-617.

 

·         V. Tabatabaee and L. Tassiulas, "MNCM: A new class of scheduling algorithms for input-buffered switches with no speedup," in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 2003, pp. 1406-1413.

 

·         Tabatabaee, V. and Tassiulas, L. 2009. MNCM: a critical node matching approach to scheduling for input buffered switches with no speedup. IEEE/ACM Trans. Netw. 17, 1 (Feb. 2009), 294-304.

 

·         Gagan Raj Gupta, Sujay Sanghavi, and Ness B. Shroff. Node Weighted Scheduling, http://www.citebase.org/abstract?id=oai:arXiv.org:0902.1169, 2009.

 

 

 

·         Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993 Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc.

 

·         Ghosh, D., Goldengorin, B., Gutin, G., Jäger, G.: Tolerance-based greedy algorithms for the traveling salesman problem. Communic. DQM 10, 52-70 (2007).

 

·         Kalagnanam, J. R., Dawande, M. W., Trumbo, M., and Lee, H. S. 2000. The Surplus Inventory Matching Problem in the Process Industry. Oper. Res. 48, 4 (Jul. 2000), 505-516.

 

·         Crescenzi P., Deng X., and Papadimitriou C. On Approximating a Scheduling Problem. Journal of Combinatorial Optimization. Springer Netherlands. Volume 5, Number 3, 2001. Pages 287-297.

 

 

·         Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. 2007. AdWords and generalized online matching. J. ACM 54, 5 (Oct. 2007), 22.

 

·         D. L. Segev, S. E. Gentry, D. S. Warren, B. Reeb, and R. A. Montgomery. Kidney paired donation and optimizing the use of live donor organs. Journal of the American Medical Association, 293(15):1883--1890, April 2005.

 

·         Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004."Pairwise Kidney Exchange," Game Theory and Information 0408001, EconWPA, revised 16 Feb 2005.

 

·         Goel, G. and Mehta, A. 2008. Online budgeted matching in random input models with applications to Adwords. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, January 20 - 22, 2008). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 982-991.

 

·         Gulati, S. and Malcolm, S. A. 2001. Call center scheduling technology evaluation using simulation. In Proceedings of the 33nd Conference on Winter Simulation (Arlington, Virginia, December 09 - 12, 2001). Winter Simulation Conference. IEEE Computer Society, Washington, DC, 1438-1442.

 

·         Ahuja, Ravindra K., 1956- & Orlin, James B., 1953-, 1998. "A fast algorithm for the bipartite node weighted matching problmem on path graphics with application to the inverse spanning tree problem," Working papers WP 4006-98., Massachusetts Institute of Technology (MIT), Sloan School of Management.

 

·         Asratian, A. S., Denley, T. M., and Häggkvist, R. 1998 Bipartite Graphs and their Applications. Cambridge University Press.

 

·         Gilbert, J. R. and Zmijewski, E. 1987. A parallel graph partitioning algorithm for a message-passing multiprocessor. Int. J. Parallel Program. 16, 6 (Dec. 1987), 427-449.

 

·         Cheng, C., McDermid, E., and Suzuki, I. 2008. A unified approach to finding good stable matchings in the hospitals/residents setting. Theor. Comput. Sci. 400, 1-3 (Jun. 2008), 84-99.

 

·         D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962.

 

·         Weimer, M., Karatzoglou, A., and Smola, A. 2008. Improving maximum margin matrix factorization. Mach. Learn. 72, 3 (Sep. 2008), 263-276.

 

Communication:

The current list is a preliminary exploration of the applications and we are interested in learning about existing (that are not mentioned here) as well as novel applications of the matching problem. Please contact us with your suggestions:

 

Mahantesh Halappanavar (mhalappa –at– odu –dot– edu)

Alex Pothen (apothen –at– purdue  –dot– edu)

Florin Dobrian (dobrain –at– cs –dot– odu –dot– edu)

 

Last updated ... April 24, 2009