A Unified Framework for Integer Programming Formulation of Graph Matching Problems

Authors

  • Bahram Alidaee University of Mississippi
  • Haibo Wang Texas A&M International University
  • Hugh Sloan The University of Mississippi

Keywords:

Combinatorial optimization, graph matching, integer programming, quadratic assignment problem

Abstract

Graph theory has been a powerful tool in solving difficult and complex problems arising in all disciplines. In particular, graph matching is a classical problem in pattern analysis with enormous applications. Many graph problems have been formulated as a mathematical program then solved using exact, heuristic and/or approximated-guaranteed procedures. On the other hand, graph theory has been a powerful tool in visualizing and understanding of complex mathematical programming problems, especially integer programs. Formulating a graph problem as a natural integer program (IP) is often a challenging task. However, an IP formulation of the problem has many advantages. Several researchers have noted the need for natural IP formulation of graph theoretic problems. The aim of the present study is to provide a unified framework for IP formulation of graph matching problems. Although there are many surveys on graph matching problems, however, none is concerned with IP formulation. This paper is the first to provide a comprehensive IP formulation for such problems. The framework includes variety of graph optimization problems in the literature. While these problems have been studied by different research communities, however, the framework presented here helps to bring efforts from different disciplines to tackle such diverse and complex problems. We hope the present study can significantly help to simplify some of difficult problems arising in practice, especially in pattern analysis.

Author Biographies

Bahram Alidaee, University of Mississippi

Professor of Operations and Supply Chian Management

Haibo Wang, Texas A&M International University

Sanchez School of Business

Hugh Sloan, The University of Mississippi

School of Business Administration

References

Calamoneri T. The L(h,k)-Labelling Problem: A Survey and Annotated Bibliography. The Computer Journal 2006; 49(5): 585-608. http://dx.doi.org/10.1093/comjnl/bxl018 A Unified Framework for Integer Programming Formulation Journal of Advances in Management Sciences & Information Systems, 2015, Volume 1 29

Diaz J, Petit J, Serna M. A Survey of Graph Layout Problems. ACM Computing Surveys 2002; 34(3): 313-356. http://dx.doi.org/10.1145/568522.568523

Gallian J. A Survey: recent results, Conjectures, and Open Problems in Labeling Graphs. Journal of Graph Theory 1989; 13: 491-504. http://dx.doi.org/10.1002/jgt.3190130410

Gallian J. A Guide to the Graph Labeling Zoo. Discrete Applied Mathematics 1994; 49: 213-229. http://dx.doi.org/10.1016/0166-218X(94)90210-0

Gallian J. A Dynamics Survey of Graph Labeling 2010; November 13.

Gurski F. Linear Layouts Measuring Neighbourhoods in Graphs. Discrete Mathematics 2006; 306: 1637-1650. http://dx.doi.org/10.1016/j.disc.2006.03.048

Lai Y-L, Williams K. A Survey of Solved Problems and Applications on Bandwidth, Edgesum, and Profile of Graphs. Journal of Graph Theory 1999; 31: 75-94. http://dx.doi.org/10.1002/(SICI)1097- 0118(199906)31:23.0.CO;2-S

Romanowski C, Nagi R, Sudit M. Data Mining in an Engineering Design Environment: OR Applications from Graph Matching. Computers and Operations Research 2006; 33: 3150-3160. http://dx.doi.org/10.1016/j.cor.2005.01.025

Yeh KR. A Survey of Labeling Graphs with a Condition at Distance Two. Discrete Mathematics 2006; 306: 1217-1231. http://dx.doi.org/10.1016/j.disc.2005.11.029

Meyer C, Jaumard B. Equivalence of Some LP-based Lower Bounds for the Golomb Ruler Problem. Discrete Applied Mathematics 2006; 154(1): 120-144. http://dx.doi.org/10.1016/j.dam.2005.07.006

Toran J. On the Hardness of Graph Isomorphism. SIAM J. Comput 2004; 33: 1093-1108. http://dx.doi.org/10.1137/S009753970241096X

Bar-Yehuda R, Bendel K, Freund A, Rawitz D. Local ratio: A Unified Framework for Approximation Algorithms. ACM Computing Surveys 2004; 36(4): 422-463. http://dx.doi.org/10.1145/1041680.1041683

Blum C, Roli A. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys 2003; 35(3): 268-308. http://dx.doi.org/10.1145/937503.937505

Chandru V, Rao R. Combinatorial Optimization and Network Algorithms. ACM Computing Surveys 1996; 28(1): 55-58. http://dx.doi.org/10.1145/234313.234341

Galil Z. Efficient Algorithms for Finding Maximum Matching in Graphs. ACM Computing Surveys 1986; 18(1): 23-38. http://dx.doi.org/10.1145/6462.6502

Sofianopoulos S. The Process Allocation Problem: a Survey of the Application of Graph-Theoretic and Integer Programming Approaches. Journal of the Operational research Society 1992; 43(5): 407-413. http://dx.doi.org/10.1057/jors.1992.67

Atamturk A, Nemhauser GL, Savelbergh M. Conflict Graphs in Solving Integer Programming Problems. European Journal of Operational Research 2000; 121: 40-55. http://dx.doi.org/10.1016/S0377-2217(99)00015-6

Christofides N, Benavent E. An Exact Algorithm for the Quadratic Assignment Problem on a Tree. Operations Research 1989; 37: 760-768. http://dx.doi.org/10.1287/opre.37.5.760

Khuller S, Raghavachari B. Graph and Network Algorithms. ACM Computing Surveys 1996; 28(1): 43-45. http://dx.doi.org/10.1145/234313.234334

Gómez D, Montero J, Yáñez J, Poidomani C. A Graph Coloring Approach for Image Segmentation. OMEGA 2007; 35: 173-183. http://dx.doi.org/10.1016/j.omega.2005.05.003

Grady L, Schwartz E. Isoperimetric Graph Partitioning for Image Segmentation, IEEE Trans. Pattern Analysis and Machine Intelligence 2006; 28(3): 469-475. http://dx.doi.org/10.1109/TPAMI.2006.57

Huang Y, Liu Q, Lv F, Gong Y, Mtaxas D. Unsupervised Image Categorization by Hypergraph Partition. IEEE Trans. Pattern Analysis and Machine Intelligence 2011; 33(6): 1266-1273. http://dx.doi.org/10.1109/TPAMI.2011.25

Unsalan C, Boyer KL. A Theoretical and Experimental Investigation of Graph Theoretical Measures for Land Development in Satellite Imagery. IEEE Trans. Pattern Analysis and Machine Intelligence 2005; 27(4): 575-589. http://dx.doi.org/10.1109/TPAMI.2005.65

Chu W, Ghahramani Z, Podtelezhnikov A, Wild D. Bayesian Segmental Models with Multiple Sequence Alignment Profiles for Protein Secondary Structure and Contact Mp Prediction. IEEE/ACM Transactions on Computational Biology and Bioinformatics 2006; 3(2): 99-113.

Venkatachalam B, Apple J, St. John K, Gusfield D. Untangling Tanglegrams: Comparing Trees by Their Drawings. IEEE/ACM Transactions on Computational Biology and Bioinformatics 2010; 7(4): 588-597. http://dx.doi.org/10.1109/TCBB.2010.57

Zhu Q, Adam Z, Choi V, Sankof D. Generalized Gene Adjacencies, Graph Bandwidth, and Clusters in Yeast Evolution. IEEE/ACM Transactions on Computational Biology and Bioinformatics 2009; 6(2): 213-220. http://dx.doi.org/10.1109/TCBB.2008.121

Reid E, Chen H. Mapping the Contemporary Terrorism Research Domain. International Journal of Human-Computer Studies 2007; 65(1): 42-56. http://dx.doi.org/10.1016/j.ijhcs.2006.08.006

Even G, Naor J, Rao S, Schieber B. Divide-and-Conquer Approximation Algorithms via Spreading Metrics. Journal of ACM 2000; 47(4): 585-616. http://dx.doi.org/10.1145/347476.347478

Kleinberg J, Tardos E. Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Field. Journal of ACM 2002; 49: 616-630. http://dx.doi.org/10.1145/585265.585268

Chekuri C, Khanna S, Naor J, Zosin L. A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM J Discrete Math 2005; 18: 608-625. http://dx.doi.org/10.1137/S0895480101396937

Greenberg H, Hart W, Lancia G. Opportunities for Combinatorial Optimization in Computational Biology. INFORMS Journal on Computing 2004; 16(3): 211-232. http://dx.doi.org/10.1287/ijoc.1040.0073

Junger M, Lee E, Mutzel P, Odenthal T. A Polyhedral Approach to the Multi-Layer Crossing Number Problem, Springer-Verlag 1997.

Luttamaguzi J, Pelsmajer M, Shen Z, Yang B. Integer Programming Solutions for Several Optimization Problems in Graph Theory, DIMACS Technical Report 2005-02, January 2005.

Almoahamad AH, Duffuaa SO. A Linear Programming Approach for the Weighted Graph Matching Problem," IEEE Trans. Pattern Analysis and Machine Intelligence 1993; 15(5): 522-525. http://dx.doi.org/10.1109/34.211474

Pinana E, Plana I, Campos V, Martri R. GRASP and Path Relinking for the Matrix Bandwidth Minimization. European Journal of Operational Research 2004; 153: 200-210. http://dx.doi.org/10.1016/S0377-2217(02)00715-4

Grotschel M, Junger M, Reinelt GA. A Cutting Plane Algorithm for the Linear Ordering Problem. Operations Research 1984; 32: 1195-1220. http://dx.doi.org/10.1287/opre.32.6.1195 30 Journal of Advances in Management Sciences & Information Systems, 2015, Volume 1 Alidaee et al.

Grotschel M, Junger M, Reinelt GA. Facets of Linear Ordering Polytope. Mathematical Programming 1985; 33: 43- 60. http://dx.doi.org/10.1007/BF01582010

Eshghi K, Azimi P. Applications of Mathematical Programming in Graceful Labeling Graphs. Journal of Applied Mathematics 2004; 1: 1-8. http://dx.doi.org/10.1155/S1110757X04310065

Junger M, Mutzel P. 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms. Journal of Graph Algorithms and Applications 1997; 1(1): 1-25. http://dx.doi.org/10.7155/jgaa.00001

Lorentz R, Nilssen R. Application of Linear Programming to the Optimal Difference Triangle Set problem. IEEE Transactions on Information Theory 1991; 37(5): 1486-1488. http://dx.doi.org/10.1109/18.133274

Caprara A, Lancia G, Carr B, Walenez B, Istrail S. 1001 Optimal PDB Structure Alignments: Integer Programming Methods for Finding the Maximum Contact Map Overlap, Journal of Computational Biology 2004; 11(1): 27-52. http://dx.doi.org/10.1089/106652704773416876

Arora S. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and Other Geometric Problems. Journal of the ACM 1998; 45(5): 753-782. http://dx.doi.org/10.1145/290179.290180

Hero A, Michel O. Asymptotic Theory of Greedy Approximations to Minimal k-Point Random Graphs. IEEE Transactions on Information Theory 1999; 45(6): 1921-1938. http://dx.doi.org/10.1109/18.782114

Lawler E, Lenstra J, Kan R, Shmoys D. The Traveling Salesman Problem, John-Wiley & Sons, Chichester 1990.

Langevin A, Soumis F, Desrosiers J. Classification of Traveling Salesman Problem Formulations. Operations Research Letters 1990; 9: 127-132. http://dx.doi.org/10.1016/0167-6377(90)90052-7

Orman AJ, Williams HP. A survey of different integer programming formulations of the travelling salesman problem, Springer 2006.

Liu D-F. T-Colorings of Graphs. Discrete Mathematics 1992; 101: 203-212. http://dx.doi.org/10.1016/0012-365X(92)90603-D

Roberts F. T-colorings of Graphs: Recent Results and Open Problems. Discrete Mathematics 1991; 93: 229-245. http://dx.doi.org/10.1016/0012-365X(91)90258-4

Shen C-C, Tsai W-H. A Graph Matching Approach to Optimal Task Assignment in Distributed Computing Systems using a Minimax Criterion. IEEE Transactions on Computers 1985; 34(4): 197-203. http://dx.doi.org/10.1109/TC.1985.1676563

Ernst A, Jiang H, Krishnamoorthy M. Exact Solutions to Task Allocation Problems. Management Science 2006; 52(10): 1634-1646. http://dx.doi.org/10.1287/mnsc.1060.0578

Lewis M, Alidaee B, Kochenberger G. Using xQx to Model and Solve the Uncapacitated Task Allocation Problem. Operations Research Letters 2005; 33(2): 176-182. http://dx.doi.org/10.1016/j.orl.2004.04.014

Menon S. Effective Reformulations for Task Allocation in Distributed Systems with a Large Number of Communicating Tasks. IEEE Transactions on Knowledge and Data Engineering 2004; 12: 1497-1508.

Stone HS. Multiprocessor Scheduling with the Aid of Network Flow Algorithms. IEEE Trans of Software Engineering 1977; 3(1): 93-95. http://dx.doi.org/10.1109/tse.1977.233840

Escoffier B, Monnot J, Paschos V. Weighted Coloring: Future Complexity and Approximability Results. Information Processing Letters 2006; 97: 98-103. http://dx.doi.org/10.1016/j.ipl.2005.09.013

Guan DJ, Zhu X. A Coloring Problem for Weighted Graphs. Information Processing Letters 1997; 61(2): 77-81. http://dx.doi.org/10.1016/S0020-0190(97)00002-1

Hassin R, Monnot J. The Maximum Saving Partition Problem. Operations Research Letters 2005; 33: 242-248. http://dx.doi.org/10.1016/j.orl.2004.07.007

Malaguti E, Monaci M, Toth P. Models and Heuristic Algorithm for a Weighted Vertex Coloring Problem. Journal of Heuristics 2009; 15(5): 503-526. http://dx.doi.org/10.1007/s10732-008-9075-1

Barbarossa S, Scutari G. Decentralized Maximum-Likelihood Estimation for Sensor Networks Composed of Nonlinearly Coupled Dynamical Systems. IEEE Transactions on Signal Processing 2007; 55(7): 3456-3470. http://dx.doi.org/10.1109/TSP.2007.893921

Li Z, Li B, Lau LC. A Constant Bound on Throughput Improvement of Multicast Network Coding in Undirected Networks. IEEE Transactions on Information Theory 2009; 55(3): 1016-1026. http://dx.doi.org/10.1109/TIT.2008.2011516

Yen CK. The Edge-orientation Problem and Some of its Variants on Weighted Graphs, Information Sciences 2006; 176(19): 2791-2816. http://dx.doi.org/10.1016/j.ins.2005.09.001

Sadigh AN, Mozafari M, Kashan AH. A Mixed Integer Linear Program and Tabu Search Approach for the Complementary Edge Covering Problem. Advances in Engineering Software 2010; 41: 762-768. http://dx.doi.org/10.1016/j.advengsoft.2009.12.017

Shih F, Cheng S. Adaptive Mathematical Morphology for Edge Linking. Information Sciences 2004; 167(1-4): 9-21. http://dx.doi.org/10.1016/j.ins.2003.07.020

Yang SJ. Efficient Algorithms to Solve the Link-orientation Problem for Multi-square, Convex-bipartite, and Convex-split Networks. Information Sciences 2005; 171(4): 475-493. http://dx.doi.org/10.1016/j.ins.2004.11.008

Biedl T, Chan T, Gnjali Y, Hajiaghayi MT, Wood D. Balanced vertex-orderings of Graphs. Discrete Applied Mathematics 2005; 148: 27-48. http://dx.doi.org/10.1016/j.dam.2004.12.001

Banerjee S, Mukherjee B, Sarkar D. Heuristic Algorithms for Constructing Optimized Structures of Linear Multihop Lightwave Networks. IEEE Transactions on Communications 1994; 42(2/3/4): 1811-1826.

Mak W-K, Young EFY. Temporal Logic Replication for Dynamically Reconfigurable FPGA Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 2003; 22(7): 952-959. http://dx.doi.org/10.1109/TCAD.2003.814237

Borndofer R, Eisenblatter A, Grotschel M, Martin A. A. Frequency Assignment in Cellular Phone Networks. Annals of Operations Research 1998; 76: 73-93. http://dx.doi.org/10.1023/A:1018908907763

Montemanni R, Smith DH, Allen S. Lower Bounds for Fixed Spectrum Frequency Assignment. Annals of Operations Research 2001; 107: 237-250. http://dx.doi.org/10.1023/A:1014911401612

Montemanni R, Moon JNJ, Smith DH. An Improved Tabu Search Algorithm for the Fixed-Spectrum FrequencyAssignment Problem. IEEE Transactions on Vehicular Technology 2003; 52(3): 891-901. http://dx.doi.org/10.1109/TVT.2003.810976

Montemanni R, Smith DH, Allen SM. An Improved Algorithm to Determine Lower Bounds for the Fixed Spectrum Frequency Assignment Problem. European Journal of Operational Research 2004; 156: 736-751. http://dx.doi.org/10.1016/S0377-2217(03)00127-9

Pardalos P, Rendl F, Wolkowicz H. The Quadratic Assignment problem: A Survey and Recent Developments, A Unified Framework for Integer Programming Formulation Journal of Advances in Management Sciences & Information Systems, 2015, Volume 1 31 American Mathematical Society, Providence, Rhode Island, USA 1994.

Loiola EM, De Abreu NM, Boaventura-Netto P, Hahn P, Querido T. A Survey for the Quadratic Assignment Problem. European Journal of Operational Research 2007; 176(2): 657-690. http://dx.doi.org/10.1016/j.ejor.2005.09.032

Chiang W-C, Kouvelis P, Urban T. Incorporating Workflow Interference in Facility Layout Design: The Quartic Assignment Problem. Management Science 2002; 48(4): 584-590. http://dx.doi.org/10.1287/mnsc.48.4.584.206

Chiang W-C, Kouvelis P, Urban T. Single- and Multi-objective Facility Layout with Workflow Interference Considerations. European Journal of Operational Research 2006; 174(3): 1414-1426. http://dx.doi.org/10.1016/j.ejor.2005.03.007

Garey M, Johnson D. Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco 1991.

Vashist A, Kulikowski C, Muchnik I. Ortholog Clustering on a Multipartite Graph, IEEE/ACM Transactions on Computational Biology and Bioinformatics 2007; 4(1): 17-27. http://dx.doi.org/10.1109/TCBB.2007.1004

Guha S. Nested Graph Dissection and Approximation Algorithms. 41st Annual Symposium on Foundation of Computer Science 2000; November 12-14. http://dx.doi.org/10.1109/sfcs.2000.892072

Lopes IC, Val´erio de Carvalho JM. An integer programming model for the Minimum Interval Graph Completion Problem. Electronic Notes in Discrete Mathematics 2010; 36: 583-590. http://dx.doi.org/10.1016/j.endm.2010.05.074

Tsao Y-P, Chang GJ. Profile Minimization on Products of Graphs. Discrete Mathematics 2006; 306: 792-800. http://dx.doi.org/10.1016/j.disc.2006.01.015

Chen H-F, Lee DT. On Crossing Minimization Problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 1998; 17(5): 406-418. http://dx.doi.org/10.1109/43.703928

Herman I, Melancon G, Marshall MS. Graph Visualization and Navigation in Information Visualization: A Survey. IEEE Transactions on Visualization and Computer Graphics 2000; 6(1): 24-43. http://dx.doi.org/10.1109/2945.841119

Laguna M, Marti R. GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization. INFORMS Journal on Computing 1999; 11: 44-52. http://dx.doi.org/10.1287/ijoc.11.1.44

Laguna M, Marti R, Valls V. Arc Crossing Minimization in Hierarchical Digraphs with Tabu Search. Computers and Operations Research 1997; 24(12): 1175-1186. http://dx.doi.org/10.1016/S0305-0548(96)00083-4

Miller R, Stout QF. Geometric Algorithms for Digitized Pictures on a Mesh Connected Computer. IEEE Trans. Pattern Anal Machine Intell 1985; 7: 216-228. http://dx.doi.org/10.1109/TPAMI.1985.4767645

Nollenburg M, Wolff A. Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming. IEEE Transactions on Visualization and Computer Graphics 2011; 17(5): 626-641. http://dx.doi.org/10.1109/TVCG.2010.81

Garey M, Johnson D. Crossing Number is NP-complete. SIAM J Alg Disc Meth 1983; 4(3): 312-316. http://dx.doi.org/10.1137/0604033

Valls V, Marti R, Lino P. A Tabu Thresholding Algorithm for Arc Crossing Minimization in Bipartite Graphs. Annals of Operations Research 1996; 63: 233-251. http://dx.doi.org/10.1007/BF02125456

Eades P, Whitesides S. Drawings Graphs in Two Layers. Theoretical Computer Science 1994; 131: 361-374. http://dx.doi.org/10.1016/0304-3975(94)90179-1

Finocchi I. Crossing-constrained hierarchical drawings. Journal of Discrete Algorithms 20064(2): 299-312. http://dx.doi.org/10.1016/j.jda.2005.06.001

Zheng L, Song L, Eades P, Crossing Minimization Problems of Drawing Bipartite Graphs in Two Clusters, APVis '05 proceedings of the 2005 Asia-Pacific symposium on Information visualisation-Vo. 45 2005.

Carpano MJ. Automatic Display of Hierarchized Graphs for Computer-Aided Decision Analysis, IEEE Trans. Systems, Man and Cybernetics 1980; 10(11): 705-715. http://dx.doi.org/10.1109/TSMC.1980.4308390

Conte D, Foggia P, Sansone C, Vento M. Thirty Years of Graph Matching in Pattern Recognition. International Journal of Pattern Recognition and Artificial Intelligence 2004; 18(3): 265-298.

Erdos P, Hedetniemi S, Laskar R, Prins G. On the Equality of the Partial Grundy and Upper Ochromatic Numbers of Graphs. Discrete Mathematics 2003; 272: 53-64. http://dx.doi.org/10.1016/S0012-365X(03)00184-5

Goldman D, Istrail S, Papadimitriou C. Algorithm Aspects of Protein Structure Similarity, IEEE Computer Society Press) 1999; pp. 512-521.

Griggs JR, Yeh R. Labeling Graphs with a Condition at Distance 2. SIAM J Discrete Math 1992; 5: 586-595. http://dx.doi.org/10.1137/0405048

Holmgren A. Using Graph Models to Analyze the Vulnerability of Electric Power Networks. Risk Analysis 2006; 26(4): 955-969. http://dx.doi.org/10.1111/j.1539-6924.2006.00791.x

Jin XT, Yeh R. Graph Distance-Dependent Labeling Related to Code Assignment in Computer Networks. Naval Research Logistics 2004; 51: 1-8.

Malafiejski M. Sum coloring of graphs. In: M. Kubale, Editor, Graph colorings, American Mathematical Society 2004; pp, 55-66. http://dx.doi.org/10.1090/conm/352/06372

Sohn J. Evaluating the Significance of Highway Network Links Under the Flood Damage: An Accessibility Approach. Transportation Research Part A 2006; 40: 491-506. http://dx.doi.org/10.1016/j.tra.2005.08.006

Voth D. TIA Program Researches Terrorism Patterns. IEEE Intelligent Systems 2003; 18(4): 4-6. http://dx.doi.org/10.1109/MIS.2003.1217620

Wang H, Alidaee B, Glover F, Kochenberger G. Solving Group Technology Problems via Clique Partitioning. International Journal of Flexible Manufacturing Systems 2007; 18(2): 77-97. http://dx.doi.org/10.1007/s10696-006-9011-3

Wang H, Obremski T, Alidaee B, Kochenberger G. Clique Partitioning for Clustering: A Comparison with K-means and Latent Class Analysis. Communications in Statistics - Simulation and Computation 2008; 37(1): 1-13. http://dx.doi.org/10.1080/03610910701723559

Guttin G, Punnen A. The Traveling Salesman Problem and Its Variations. Kluwer Academic Publishers, Dordrecht 2002.

Vairaktarakis G. On Gilmore-Gomory’s Open Question for the Bottleneck TSP. Operations Research Letters 2003; 31: 483-491. http://dx.doi.org/10.1016/S0167-6377(03)00050-6

Vairaktarakis G. Simple Algorithms for Gilmore-Gomory’s Traveling Salesman and Related Problems. Journal of Scheduling 2003; 6: 499-520. http://dx.doi.org/10.1023/A:1026200209386 32 Journal of Advances in Management Sciences & Information Systems, 2015, Volume 1 Alidaee et al.

Bhusnurmath A, Taylor CJ. Graph Cuts via Norm Minimization. IEEE Transaction on Pattern Analysis and Machine Intelligence 2008; 30(10): 1866-1871. http://dx.doi.org/10.1109/TPAMI.2008.82

Chai SM, Chiricescu S, Essick R, Lucas B, May P, Moat K, Norris JM, Schuette M, López-Lagunas A. Streaming Processors for Next-Generation Mobile Imaging Applications. IEEE Communications Magazine 2005; 43(12): 81-89. http://dx.doi.org/10.1109/MCOM.2005.1561924

Klemm RP. WebCompanion: A Friendly Client-Side Web Prefetching Agent. IEEE Transactions on Knowledge and Data Engineering 1999; 11(4): 577-594. http://dx.doi.org/10.1109/69.790809

Charon I, Hudrey O. An Updated Survey on the Linear Ordering Problem for Weighted or Unweighted Tournaments. Ann Oper Res 2010; 175: 107-158. http://dx.doi.org/10.1007/s10479-009-0648-7

Haralick RM, Kartus J. Arrangements, homomorphisms, and discrete relaxation. IEEE Trans Syst Man Cybern SMC 1978; 8: 600-612. http://dx.doi.org/10.1109/TSMC.1978.4310036

Guan DJ, Williams K. Profile Minimization on Triangulated Triangles. Discrete Mathematics 2003; 260: 69-76. http://dx.doi.org/10.1016/S0012-365X(02)00450-8

Lai Y-L, Chang G. On the Profile of the Corona of Two Graphs. Information Processing Letters 2004; 89: 287-292. http://dx.doi.org/10.1016/j.ipl.2003.12.004

Cunningham P. A Taxonomy of Similarity Mechanisms for Case-Based Reasoning. IEEE Transactions on Knowledge and data Engineering 2009; 21(11): 1532-1543. http://dx.doi.org/10.1109/TKDE.2008.227

Kimelman D, Kimelman M, Mandelin D, Yellin DM. Bayesian Approaches to Matching Architectural Diagrams. IEEE Transactions on Software Engineering 2010; 36(2): 348-274. http://dx.doi.org/10.1109/TSE.2009.56

Messmer BT, Bunke H. Efficient Subgraph Isomorphism Detection: A Decomposition Approach. IEEE Transactions on Knowledge and data Engineering 2000; 12(2): 307-323. http://dx.doi.org/10.1109/69.842269

Wong JL, Kourshanfar F, Potkonjak M. Flexible ASIC: shared masking for multiple media processors, Proceedings of 42nd Design Automation Conference, June 13-17 2005; pp. 909- 914. http://dx.doi.org/10.1145/1065579.1065818

Horaud R, Sossa H. Polyhedral Object Recognition by Indexing. Pattern Recognition 1995; 28(12): 1855-1870. http://dx.doi.org/10.1016/0031-3203(95)00048-8

Mateus D, Cuzzolin F, Horaud R, Boyer E. Articulated Shape Matching Using Locally Linear Embedding and Orthogonal Alignment. IEEE 11th International Conference on Computer Vision 2007. ICCV 2007; pp. 1-8. http://dx.doi.org/10.1109/iccv.2007.4409180

Medaglia L, Fang SC. A Genetic-based Framework for Solving (Multi-criteria) Weighted Matching Problems. European Journal of Operational Research 2003; 149: 77-101. http://dx.doi.org/10.1016/S0377-2217(02)00484-8

Barrow HG, Burstall RM. Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques. Information Processing Letters 1976; 4: 83-84. http://dx.doi.org/10.1016/0020-0190(76)90049-1

Al-Kofahi Y, Lassoued W, Lee W, Roysam B. Improved Automatic Detection and Segmentation of Cell Nuclei in Histopathology Images. IEEE Transactions on Biomedical Engineering 2010; 54(4): 841-852. http://dx.doi.org/10.1109/TBME.2009.2035102

Chalopin J, Paulusma D. Graph Labelings Derived from Models in Distributed Computing: A Complete Complexity Classification. Networks 2011; pp. 1-25. http://dx.doi.org/10.1002/net.20432

Haralick RM, and Shapiro L. The Consistent Labeling Problem: Part I. IEEE Trans Pattern Anal Machine Intell PAMI 1979; 1(2): 173-184. http://dx.doi.org/10.1109/TPAMI.1979.4766903

Haralick RM, Shapiro L. The Consistent Labeling Problem: Part II. IEEE Trans Pattern Anal Machine Intell PAMI 1980; 2(3): 193-203. http://dx.doi.org/10.1109/TPAMI.1980.4767007

Hausner A. A new clustering algorithm for coordinate-free data. Pattern Recognition 2010; 43: 1306-1319. http://dx.doi.org/10.1016/j.patcog.2009.10.018

Karpovsky MG, Levitin LB. Data Verification and Reconciliation With Generalized Error-Control Codes. IEEE Transactions on Information Theory 2003; 49(7): 1788-1793. http://dx.doi.org/10.1109/TIT.2003.813498

Kroon LG, Sen A, Deng H, Roy A. The Optimal Cost Chromatic Partition Problem for Trees and Interval Graphs, WG '96 Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, SpringerVerlag, London, UK 1997.

Nicoloso S. Sum Coloring and Interval Graphs: A Tight Upper Bound for the Minimum Number of Colors. Discrete Mathematics 2004; 280: 251-257. http://dx.doi.org/10.1016/j.disc.2003.06.015

Supowit KJ. Finding a Maximum Planar Subset of a Set of Nets in Channel. IEEE Trans Comput Aided Design 1987; 6(1): 93-94. http://dx.doi.org/10.1109/TCAD.1987.1270250

Kubicka E. The Chromatic Sum of Graph, Western Michigan University, Kalamozoo 1989.

Butenko S, Festa P, Pardalos P. On the Chromatic Number of Graphs. Journal of Optimization Theory and Applications 2001; 109(1): 69-83. http://dx.doi.org/10.1023/A:1017557620292

Kochenberger G, Glover F, Alidaee B, Wang H. Clustering of Microarray Data via Clique Partitioning. Journal of Combinatorial Optimization 2005; 10: 77-92. http://dx.doi.org/10.1007/s10878-005-1861-1

Lin L, Liu X, Zhu S-C. Layered Graph Matching with Composite Cluster Sampling. IEEE Trans. Pattern Analysis and Machine Intelligence 2010; 32(8): 1426-1442. http://dx.doi.org/10.1109/TPAMI.2009.150

Santos JM, de Sa´ JM, Alexandre LA. LEGClust—A Clustering Algorithm Based on Layered Entropic Subgraphs. IEEE Trans. Pattern Analysis and Machine Intelligence 2008; 30(1): 62-75. http://dx.doi.org/10.1109/TPAMI.2007.1142

Soundararajan P, Sarkar S. An In-Depth Study of Graph Partitioning Measures for Perceptual Organization. IEEE Trans. Pattern Analysis and Machine Intelligence 2003; 25(6): 642-660. http://dx.doi.org/10.1109/TPAMI.2003.1201817

Yoo JS, Shekar S. A Joinless Approach for Mining Spatial Colocation Patterns. IEEE Transactions on Knowledge and Data Engineering 2006; 18(10): 1323-1337. http://dx.doi.org/10.1109/TKDE.2006.150

Grotschel M, Wakabayashi Y. A Cutting Plane Algorithm for a Clustering Problem. Mathematical Programming 1989; 45: 59-96. http://dx.doi.org/10.1007/BF01589097

Grotschel M, Wakabayashi Y. Facets of the Clique Partitioning Polytope. Mathematical Programming 1990; 47: 367-387. http://dx.doi.org/10.1007/BF01580870

Hale W. Frequency Assignment: Theory and Application. Proc IEEE 1980; 68: 13-22. http://dx.doi.org/10.1109/PROC.1980.11899 A Unified Framework for Integer Programming Formulation Journal of Advances in Management Sciences & Information Systems, 2015, Volume 1 33

Bodlaender H, Broersma H, Fomin F, Pyatkin A, Woeginger G. Radio Labeling with Preassigned Frequencies. SIAM J Optim 2004; 15: 1-16. http://dx.doi.org/10.1137/S1052623402410181

Bodlaender H, Kloks H, Tan R, Van Leeuwen J. Approximations for of Graphs. The Computer Journal 2004; 47(2): 193-204. http://dx.doi.org/10.1093/comjnl/47.2.193

Erwin D, George J, Mauro D. On Labeling the Vertices of Products of Complete Graphs with Distance Constraints. Naval Research Logistics 2003; 50: 1-6.

Griggs JR, Král D. Graph labellings with variable weights, a survey. Discrete Applied Mathematics 2009; 157: 2646-2658.

Fiala J, Kral D, Skrekovski R. A Brooks-type Theorem for the Generalized List T-coloring. SIAM journal of Discrete Methods 2005; 19(3): 588-609.

Kral D. The Channel Assignment Problem with Variable Weights. SIAM Journal of Discrete Methods 2006; 20(3): 690-704. http://dx.doi.org/10.1137/040619636

Graf A. Distance Graphs and the T-coloring Problem. Discrete Mathematics 1999; 196: 153-166. http://dx.doi.org/10.1016/S0012-365X(98)00199-X

Boykov Y, Vekseler O, Zabih R. Fast Approximate Energy Minimization via Graph Cuts. IEEE Trans. Pattern Analysis and Machine Intelligence 2001; 23(11): 1222-1239. http://dx.doi.org/10.1109/34.969114

Jiang H, Drew MS, Li Z-N. Matching by Linear Programming and Successive Convexification. IEEE Transactions on Pattern Analysis and Machine Intelligence 2007; 29(6): 959- 975. http://dx.doi.org/10.1109/TPAMI.2007.1048

Jiang H, Yu SX, Martin DR. Linear Scale and Rotation Invariant Matching. IEEE Transactions on Pattern Analysis and Machine Intelligence 2011; 33(7): 1339-1355. http://dx.doi.org/10.1109/TPAMI.2010.212

Komodakis N, Tziritas G. Approximate Labeling via Graph Cuts Based on Linear Programming. IEEE Transactions on Pattern Analysis and Machine Intelligence 2007; 29(8): 1436- 1453. http://dx.doi.org/10.1109/TPAMI.2007.1061

Komodakis N, Paragios N, Tziritas G. MRF Energy Minimization and Beyond via Dual Decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence 2011; 33(3): 531-552. http://dx.doi.org/10.1109/TPAMI.2010.108

Werner T. A Linear Programming Approach to Max-Sum Problem: A Review. IEEE Transactions on Pattern Analysis and Machine Intelligence 2007; 29(7): 1165-1179. http://dx.doi.org/10.1109/TPAMI.2007.1036

Blackburn SR, Etzion T, Martin KM, Paterson MB. TwoDimensional Patterns With Distinct Differences— Constructions, Bounds, and Maximal Anticodes. IEEE Transactions on Information Theory 2010; 56(3): 1216-1229. http://dx.doi.org/10.1109/TIT.2009.2039046

Blackburn SR, Etzion T, Martin KM, Paterson MB. Distinct Difference Configurations: Multihop Paths and Key Predistribution in Sensor Networks. IEEE Transactions on Information Theory 2010; 56(8): 3961-3972. http://dx.doi.org/10.1109/TIT.2010.2050794

Dollas A, Rankin W, McCracken D. A New Algorithm for Golomb Ruler Derivation and Proof of the 19 Mark Ruler. IEEE Trans. Inform. Theory 199844(1): 379-382. http://dx.doi.org/10.1109/18.651068

Galinier P, Jaumard N. A Tabu Search Algorithms for Difference Triangle Sets and Golomb Rulers. Computers and Operations Research 2006; 33: 955-970. http://dx.doi.org/10.1016/j.cor.2004.08.006

Downloads

Published

2015-07-31

How to Cite

Alidaee, B., Wang, H., & Sloan, H. (2015). A Unified Framework for Integer Programming Formulation of Graph Matching Problems. Journal of Advances in Management Sciences & Information Systems, 1, 8–33. Retrieved from https://mail.lifescienceglobal.com/pms/index.php/jamsis/article/view/3011

Issue

Section

Articles