Combinatorial Algorithm frequently called Combinatorial Computing, deals with problem on how to carry out computations on discrete mathematical structures. It is all about finding patterns or arrangements that are best possible ways to satisfy certain constraints. Popularity of Combinatorial Algorithm is increasing day by day because outside the traditional areas of applications of mathematics to the physical sciences, discrete mathematical structures (e.g. permutation, graph etc.) occur more frequently than continuous ones, and the fraction of all computing time spent on problem that arise in the physical science is decreasing. Starting about 1970s, computer scientists experienced a phenomena called “Floyd’s Lemma”: problems that seemed to required n3 operations could actually be solve in O(n2); problem that seemed to require n2 time could be handled in O(nlogn) and also nlogn was often reducible to O(n). Besides this, running time of O(2n) can be reducible to O(1.5n) to O(1.3n) etc. Thus, though unlike other fields Combinatorial Algorithm does not have a few “fundamental theorem” that form the core of the subject matter and from which most of the result can be derived, the art of writing such algorithm in a tricky way or improvement of existing algorithms rather improvement in processor speeds, can save years or even centuries of computer time. Having back and forth over the territory of the Combinatorial Algorithm so often, the author is now charged to prepare the paper for looking the field from our view point in a nutshell with a special emphasize on Graph and real life applications of graph algorithms in the areas like network routing, information security, vulnerability analysis, storage of data and Coding and Information Theory.

Graph, Combinatorial Algorithms, Security, Integity, Storage Space

[1]. Reingold, E. M., Nievergelt, J., & Deo, N. (1977). Combinatorial algorithms: theory and practice. Prentice Hall College Div.
[2]. Knuth, D. E. (2005). The Art of Computer Programming. Fascicle 4A-Generating All Trees, vol. 4.
[3]. Chekuri, C., & Pal, M. (2005, October). A recursive greedy algorithm for walks in directed graphs. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on (pp. 245-253). IEEE.
[4]. Even, S. (2011). Graph algorithms. Cambridge University Press.
[5]. Reif, John H. (1985). Depth-first search is inherently sequential. Information Processing Letters. 20 (5). doi:10.1016/0020-0190(85)90024-9.
[6]. Quinn, M. J., & Deo, N. (1984). Parallel graph algorithms. ACM Computing Surveys (CSUR), 16(3), 319-348.
[7]. Erciyes, K. (2018). Distributed Graph Algorithms. In Guide to Graph Algorithms (pp. 117-136). Springer, Cham.
[8]. Graham, R. L., & Hell, P. (1985). On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1), 43-57.
[9]. Hoffman, K. L., Padberg, M., & Rinaldi, G. (2013). Traveling salesman problem. In Encyclopedia of operations research and management science (pp. 1573-1578). Springer US.
[10]. Sewell, E. C. (1996). An improved algorithm for exact graph coloring. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, 26, 359-372.
[11]. Even, G., Naor, J., Rao, S., & Schieber, B. (1999). Fast approximate graph partitioning algorithms. SIAM Journal on Computing, 28(6), 2187-2214.
[12]. Golomb, S. W., & Baumert, L. D. (1965). Backtrack programming. Journal of the ACM (JACM), 12(4), 516-524.
[13]. Wang, X., Wang, X., & Wilkes, D. M. (2009). A divide-and-conquer approach for minimum spanning tree-based clustering. IEEE Transactions on Knowledge and Data Engineering, 21(7), 945-958.
[14]. Bellman, R. (1962). Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), 9(1), 61-63.
[15]. Levitin, A., & Papalaskari, M. A. (2002, February). Using puzzles in teaching algorithms. In ACM SIGCSE Bulletin (Vol. 34, No. 1, pp. 292-296). ACM.
[16]. Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4), 704-714.
[17]. Gazit, H. (1986, October). An optimal randomized parallel algorithm for finding connected components in a graph. In Foundations of Computer Science, 1986., 27th Annual Symposium on (pp. 492-501). IEEE.
[18]. Greenberg, H. J. (1998). Greedy algorithms for minimum spanning tree. University of Colorado at Denver.
[19]. Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. The Bell system technical journal, 49(2), 291-307.
[20]. Amestoy, P. R., Davis, T. A., & Duff, I. S. (1996). An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4), 886-905.
[21]. Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An improved ant System algorithm for thevehicle Routing Problem. Annals of operations research, 89, 319-328.
[22]. Henzinger, M. R., Henzinger, T. A., & Kopke, P. W. (1995, October). Computing simulations on finite and infinite graphs. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on (pp. 453-462). IEEE.
[23]. Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical computer science, 1(3), 237-267.
[24]. Alekseev, V. E., Boliac, R., Korobitsyn, D. V., & Lozin, V. V. (2007). NP-hard graph problems and boundary classes of graphs. Theoretical Computer Science, 389(1-2), 219-236.
[25]. Mathon, R. (1979). A note on the graph isomorphism counting problem. Information Processing Letters, 8(3), 131-136.
[26]. Yuan, S. Y., & Kuo, S. Y. (1998). A new technique for optimization problems in graph theory. IEEE Transactions on Computers, 47(2), 190-196.
[27]. LEWIN, K (1936). Principles of Topological Psycology. Mc-Graw-Hill, New York.
[28]. Deo, N. (2004). “Graph theory with applications to engineering and computer science.” PHI.
[29]. Rosen, K. H. (2007). Discrete mathematics and its applications. Amc, 10(12), 824.
[30]. Madkour, A., Aref, W. G., Rehman, F. U., Rahman, M. A., & Basalamah, S. (2017). A survey of shortest-path algorithms. arXiv preprint arXiv:1705.02044.
[31]. Radhakrishnan, S., Racherla, G., Sekharan, C. N., Rao, N. S., & Batsell, S. G. (1999). DST-a routing protocol for ad hoc networks using distributed spanning trees. In Wireless Communications and Networking Conference, 1999. WCNC. 1999 IEEE (Vol. 3, pp. 1543-1547). IEEE.
[32]. Sensarma, D., &Majumder, K. “A Comparative Analysis of the Ant Based Systems for QoS Routing in MANET.” In Recent Trends in Computer Networks and Distributed Systems Security (pp. 485-496). Springer Berlin Heidelberg, 2012.
[33]. Sensarma, D., andMajumder, K.“AMTR: The ANT Based QOS Aware Multipath Temporally Ordered Routing Algorithm for MANETs”, AISC- 2013, CS & IT-CSCP 2013, pp. 389–396, 2014.
[34]. Sensarma, D., andMajumder, K. “An efficient ant based qos aware intelligent temporally ordered routing algorithm for manets.” International Journal of Computer Networks & Communications (IJCNC), Vol. 5, No. 4, PP.189-203, Jul. 2013.
[35]. Sensarma, D., and Majumder, K. “HAQR: TheHierarchical ANT based QOS aware On-demandRoutingfor MANETS.”WimoA- 2013,CS & IT-CSCP 2013, pp.193-202, 2013.
[36]. Sensarma, D., andMajumder, K. “A Novel Hierarchical Ant Based QoS aware Intelligent Routing Scheme for MANETs.” International Journal of Computer Networks & Communications (IJCNC), Vol. 5, No. 6, PP.215-229, Nov. 2013.
[37]. Sensarma, D., andMajumder, K.“IWDRA: An Intelligent Water Drop Based QoS-Aware Routing Algorithm for MANETs.” Proceedings of the International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2013. Springer International Publishing, 2014.
[38]. Rajaram, V., Kumatharan, N., & Srividhya, S. Study on Applications of Graph Theory in Wireless Sensor Networks.
[39]. Mears, C., De La Banda, M. G., & Wallace, M.,“On implementing symmetry detection.” Constraints, 14(4), 2009, 443-477.
[40]. Albertson, Michael O., and Karen L. Collins. “Symmetry breaking in graphs.” Electron. J. Combin 3, no. 1 (1996): R18.
[41]. Harary, F. R. A. N. K. “Methods of destroying the symmetries of a graph.” Bull. Malasyan Math. Sc. Soc 24, no. 2 (2001): 183-191.
[42]. Sensarma, D., and Sarma, S. S. A Unified Framework for Security and Storage of Information. International Journal of Advance Engineering and Research Development, Vol. 2, Issue 1, PP.197-203, 2015.
[43]. Kahate, A. Cryptography and network security. Tata McGraw-Hill Education, 2013.
[44]. Ustimenko, V. (2001). CRYPTIM: Graphs as tools for symmetric encryption. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Springer Berlin Heidelberg, PP. 278-286, 2001.
[45]. Ustimenko, V. “On Graph-Based Cryptography and Symbolic Computations.”Serdica Journal of Computing 1, no. 2 (2007): 131-156.
[46]. Sensarma, D., Banerjee, S., and Basuli, K. A New Scheme for Key Exchange. International Journal of Modern Engineering Research (IJMER), ISSN (Online): 2249-6645, 2(3), 2012.
[47]. Sensarma, D., and Sarma, S. S. GMDES: A GRAPH BASED MODIFIED DATA ENCRYPTION STANDARD ALGORITHM WITH ENHANCED SECURITY. International Journal of Research in Engineering and Technology, eISSN: 2319-1163, Vol. 3, Issue. 3, PP. 653-660, Mar-2014.
[48]. Shih, F. Y. Digital watermarking and steganography: fundamentals and techniques. CRC Press, 2007.
[49]. Hetzl, S., and Petra, M. “A graph–theoretic approach to steganography.” In Communications and Multimedia Security, pp. 119-128. Springer Berlin Heidelberg, 2005.
[50]. Wu, H., Wang, H., Zhao, H., & Yu, X. (2015). Multi-layer assignment steganography using graph-theoretic approach. Multimedia Tools and Applications, 74(18), 8171-8196.
[51]. Venkatesan, R., Vazirani, V., and Sinha, S. “A graph theoretic approach to software watermarking.” In Information Hiding, pp. 157-168. Springer Berlin Heidelberg, 2001.
[52]. Halder, R., Dasgupta,P.,Naskar,S., and Sarma., S. S. “An Internet-based IP Protection Scheme for Circuit Designs using Linear Feedback Shift Register-based Locking.”Engineering Letters 19, no. 2 (2011): 84.
[53]. Qu, G., &Potkonjak, M.,“Hiding signatures in graph coloring solutions.” In Information Hiding (pp. 348-367). Springer Berlin Heidelberg, (2000, January).
[54]. Kahng, A. B., Lach, J., Mangione-Smith, W. H., Mantik, S., Markov, I. L., Potkonjak, M., & Wolfe, G., “Constraint-based watermarking techniques for design IP protection.”Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 20(10), 1236-1252, 2001.
[55]. Sensarma, D., & Sarma, S. S. (2015). Data Hiding using Graphical Code based Steganography Technique. arXiv preprint arXiv:1509.08743.
[56]. Collberg, Christian S., Thomborson, C. and Gregg M. Townsend. “Dynamic graph-based software fingerprinting.” ACM Transactions on Programming Languages and Systems (TOPLAS) 29, no. 6 (2007): 35.
[57]. G. Brassard, C. Crepeau. “Non-Transitive Transfer of Confidence: A PerfectZeroKnowledge Interactive Protocol for SAT and Beyond.” Proc. of the 27th Annual Symp. on Foundations of Computer Science: 188-195, 1986.
[58]. M. Blum. “How to Prove a Theorem So No One Else Can Claim It.” Proceedings of the International Congress of Mathematicians: 1444-1451, 1986.
[59]. D. Lapidot, A. Shamir. “A one-round, two-prover, zero-knowledge protocol for NP.” Combinatorica, 15(2): 203-214, June, 1995.
[60]. Horan, V., & Gudaitis, M. (2011). Investigation of Zero Knowledge Proof Approaches Based on Graph Theory. AIR FORCE RESEARCH LAB ROME NY INFORMATION DIRECTORATE.
[61]. Sensarma, D., & Sarma, S. S. (2015). A survey on different graph based anomaly detection techniques. Indian Journal of Science and Technology, 8(31).
[62]. Liu, K., and Terzi, E. “Towards identity anonymization on graphs.” InProceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 93-106. ACM, 2008.
[63]. Zou, L., Chen, L., &Özsu, M. T. “K-automorphism: A general framework for privacy preserving network publication.” Proceedings of the VLDB Endowment, 2(1), 946-957, (2009).
[64]. Moazzami, D. (2016). Towards a measure of vulnerability, tenacity of a Graph. Journal of Algorithms and Computation, 48(1), 149-154.
[65]. Li, F., & Li, X. (2004). On the integrity of graphs. In Parallel and Distributed Computing and Systems (Vol. 16, pp. 577-582).
[66]. Le-Phuoc, D., Quoc, H. N. M., Quoc, H. N., Nhat, T. T., & Hauswirth, M. (2016). The Graph of Things: A step towards the Live Knowledge Graph of connected things. Web Semantics: Science, Services and Agents on the World Wide Web, 37, 25-35.
[67]. Angles, R., & Gutierrez, C. (2008). Survey of graph database models. ACM Computing Surveys (CSUR), 40(1), 1.
[68]. Meyerhenke, H., & Gehweiler, J. (2010). On dynamic graph partitioning and graph clustering using diffusion. In Dagstuhl Seminar Proceedings. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
[69]. Zhou, F. (2015). Graph compression. Department of Computer Science and Helsinki Institute for Information Technology HIIT, 1-12.
[70]. Chierichetti, F., Kumar, R., Lattanzi, S., Mitzenmacher, M., Panconesi, A., & Raghavan, P. (2009, June). On compressing social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 219-228). ACM.
[71]. Sensarma, D., & Sarma, S. S. (2017). A Graph Theoretic Approach for Minimizing Storage Space using Bin Packing Heuristics. INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS, 8(2), 29-39.
[72]. Sensarma, D., Banerjee, S., Basuli, K., Naskar, S., & Sarma, S. S. (2012). On an optimization technique using Binary Decision Diagram. arXiv preprint arXiv:1203.2505.
[73]. Hamming, R. W. Coding and information theory. Prentice-Hall, Inc., 1986.
[74]. Jungnickel, D., & Vanstone, S. A. (1997). Graphical codes revisited. IEEE Transactions on Information Theory, 43(1), 136-146.
[75]. Tanner, R. M., Sridhara, D., Sridharan, A., Fuja, T. E., & Costello, D. J. (2004). LDPC block and convolutional codes based on circulant matrices. IEEE Transactions on Information Theory, 50(12), 2966-2984.
[76]. Luby, M. G., Mitzenmacher, M., Shokrollahi, M. A., & Spielman, D. A. (2001). Improved low-density parity-check codes using irregular graphs. IEEE Transactions on Information Theory, 47(2), 585-598.
[77]. Gadouleau, M., & Riis, S. (2011). Graph-theoretical constructions for graph entropy and network coding based communications. IEEE Transactions on Information Theory, 57(10), 6703-6717.