A Unified Framework for Integer Programming Formulation of Graph Matching Problems
Keywords:
Combinatorial optimization, graph matching, integer programming, quadratic assignment problemAbstract
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.
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
How to Cite
Issue
Section
License
Policy for Journals/Articles with Open Access
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are permitted and encouraged to post links to their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
Policy for Journals / Manuscript with Paid Access
Authors who publish with this journal agree to the following terms:
- Publisher retain copyright .
- Authors are permitted and encouraged to post links to their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work .