On Combinatorial Algorithms with Special Emphasize on Graph and Graph Algorithms - Sensarma, Debajit (International Journal of Computer Sciences and Engineering, 2025)
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.