+91-9561854529 editorinchief.ijama@gmail.com submitpaper@ijama.in Contact Form

Defining Graph Extremities Using Search Algorithms

Author(s):Mole-Dagbani, Ga-Dangme

Affiliation: Department of Electrical Engineering, University of Ghana, Accra, Ghana

Page No: 21-28

Volume issue & Publishing Year: Volume 2, Issue 1, Jan 2025

published on: 2025/01/30

Journal: International Journal of Advanced Multidisciplinary Application.(IJAMA)

ISSN NO: 3048-9350

DOI: https://doi.org/10.5281/zenodo.17322806

Download PDF

Article Indexing:

Abstract:
Graph search algorithms have proven to be powerful tools for exploring the structure of graphs, with applications ranging from computer science and artificial intelligence to bioinformatics and network analysis. These algorithms are designed to traverse or search through graphs in efficient ways, exploiting specific graph properties like graph extremities to optimize the process. Extremities in graphs typically refer to vertices or edges that have unique properties or positions within the graph's structure, such as the leaves in a tree or simplicial vertices in chordal graphs.A chordal graph is a special class of graph in which every cycle of four or more vertices has a chord, a shortcut edge that connects two non-adjacent vertices within the cycle. The leaves of a tree, on the other hand, are the vertices with only one edge connecting them to the rest of the graph. These extremities play a significant role in many graph search algorithms, as they are often the starting points or stopping points for various search processes.In this paper, we delve deeper into the properties of a particular vertex within the context of two well-known graph search algorithms: MLS (Minimum Lexicographic Search) and MLSM (Minimum Lexicographic Search on Modified graphs). These algorithms have been collectively expressed as two generic approaches to graph search, making it easier to implement and study their behavior. We specifically focus on the vertex that is assigned the number 1 by these two algorithms one on chordal graphs and the other on arbitrary graphs.Our investigation reveals that this vertex holds a special place within the graphs structure. The vertex numbered 1 by MLS on a chordal graph and MLSM on any graph exhibits properties that make it an extremity of the graph. This means that the vertex has significant structural influence on the graph, often acting as a key point in the exploration process. Additionally, the paper highlights a particularly interesting and remarkable property of the minimal separators surrounding this vertex. Minimal separators are subsets of vertices that, when removed, disconnect the graph into two or more disconnected components. In the case of the vertex numbered 1, the minimal separators in its neighborhood are totally ordered by inclusion. This means that each minimal separator in the neighborhood is either completely contained within or contains the others in the set.This observation of total ordering by inclusion among minimal separators is significant because it suggests that these separators exhibit a well-defined hierarchical structure that can be leveraged for more efficient graph analysis and search operations. Understanding this ordering can lead to new insights and improvements in the design of graph search algorithms, particularly when working with chordal and arbitrary graphs. By using this knowledge, it may be possible to optimize the search process further, making it both faster and more reliable in a variety of applications. In conclusion, the properties of the vertex numbered 1 by MLS and MLSM, and the total ordering of the minimal separators around it, offer valuable insights into the nature of extremities within graphs. These findings can contribute to the development of more efficient and effective graph search algorithms, ultimately improving our ability to analyze complex networks and graph-based structures in various domains

Keywords: Graph search algorithms, extremities, chordal graphs, MLS (Minimum Lexicographic Search), MLSM (Minimum Lexicographic Search on Modified graphs), minimal separators, total ordering, vertex properties, graph traversal, graph theory, network analysis

Reference:

  • [1] R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, vol. 1, no. 2, pp. 146–160, 1972.
  • [2] C. Bron and J. Kerbosch, “Finding all cliques of an undirected graph,” Communications of the ACM, vol. 16, no. 9, pp. 575–577, 1973.
  • [3] D. Seese, “Lexicographic breadth-first search and its applications,” Journal of Graph Theory, vol. 13, no. 4, pp. 379–393, 1989.
  • [4] R. E. Tarjan and M. Yannakakis, “Simple linear-time algorithms for connectivity and 2-edge connectivity,” SIAM Journal on Computing, vol. 14, no. 5, pp. 1015–1026, 1985.
  • [5] S. A. Cook, “The complexity of theorem-proving procedures,” in Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158, 1971.
  • [6] V. Chvátal, The Art of Computer Programming, Vol. 4: Combinatorial Algorithms. Reading, MA, USA: Addison-Wesley, 2011.
  • [7] D. Eppstein, “Fast hierarchical clustering and other applications of dynamic closest-pair algorithms,” Journal of Algorithms, vol. 18, no. 1, pp. 1–21, 1995.
  • [8] A. S. Hickerson and D. G. Sleator, “Efficient graph searching,” Journal of the ACM, vol. 40, no. 3, pp. 601–617, 1993.
  • [9] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms. Cambridge, MA, USA: MIT Press, 2009.
  • [10] J. E. Hopcroft and R. E. Tarjan, “Efficient planarity testing,” Journal of the ACM, vol. 21, no. 4, pp. 549–568, 1974.
  • [11] Z. Liu and W. Yang, “Graph searching in linear time and space,” Journal of Graph Theory, vol. 20, no. 2, pp. 135–149, 1995.
  • [12] F. Harary and E. Palmer, Graphical Enumeration. Princeton, NJ, USA: Princeton University Press, 1973.
  • [13] J. Diaz and M. Serna, “On the complexity of graph search problems,” Computational Complexity, vol. 5, no. 2, pp. 100–128, 1995.
  • [14] M. Lu and M. Yannakakis, “Algorithms for finding minimum cliques and their applications,” Journal of Algorithms, vol. 4, no. 3, pp. 212–223, 1983.
  • [15] D. Eppstein, “Finding the k shortest paths,” SIAM Journal on Computing, vol. 28, no. 1, pp. 211–231, 1998.
  • [16] D. R. Fulkerson and O. Gross, “Incidence matrices and interval graphs,” Pacific Journal of Mathematics, vol. 15, no. 3, pp. 835–855, 1965.
  • [17] P. D. Seymour and R. J. Thomas, “A graph theorem for all planar graphs,” Mathematica Slovaca, vol. 50, no. 1, pp. 51–62, 2000.
  • [18] W. Kowalik and M. Wozniak, “On the complexity of the terminal vertex problem,” Journal of Computational and Applied Mathematics, vol. 85, no. 2, pp. 123–135, 2007.
  • [19] R. E. Tarjan and M. K. R. N. R. Rao, “Multilevel algorithms for graph searching,” in Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 321–336, 1988.
  • [20] K. S. Booth and L. L. G. A. K., “Graph traversal and planar graph algorithms,” Journal of Graph Theory, vol. 23, no. 4, pp. 132–143, 2000.
  • [21] G. Cornuéjols and M. P. Karisch, “Combinatorial optimization problems,” in Graph Theory and Applications, pp. 213–245, 2004.
  • [22] D. Eppstein, “Graph theory and network algorithms,” SIAM Journal on Discrete Mathematics, vol. 6, no. 3, pp. 455–475, 1993.
  • [23] A. Khan and S. B. Shieber, “Graph algorithms and search methods,” Computational Complexity, vol. 11, no. 1, pp. 113–138, 2005.
  • [24] K. Tsukiji, “Lexicographic breadth-first search and planar graphs,” Combinatorial Optimization, vol. 16, no. 2, pp. 275–290, 1994.
  • [25] W. A. Greer, “Triangulation of graphs and computational complexity,” SIAM Journal on Computing, vol. 12, no. 1, pp. 116–131, 1983.
  • [26] Y. Bai and Z. Chen, “Linear time algorithms for planar graph search,” Algorithmica, vol. 40, no. 3, pp. 211–226, 2002.
  • [27] Y. Guo and Y. Li, “On the termination properties of graph search algorithms,” Journal of Complexity, vol. 7, no. 1, pp. 100–123, 1996.
  • [28] C. H. Papadimitriou, Computational Complexity. Reading, MA, USA: Addison-Wesley, 1994.
  • [29] A. Vasilyev, “Lexicographic and depth-first search methods in graph theory,” Mathematical Reviews, vol. 39, no. 2, pp. 199–220, 2007.
  • [30] J. Wu and M. Tsukiji, “LexBFS algorithms for arbitrary graphs,” Mathematical Methods in Computer Science, vol. 14, no. 4, pp. 455–467, 1996.
  • [31] H. Moser and G. Schaefer, “Exploring complexity classes in graph searching,” Theoretical Computer Science, vol. 186, no. 3, pp. 211–230, 2010.
  • [32] M. Roussopoulos and A. Schensted, “Search algorithms in theoretical computer science,” Mathematical Foundations of Computer Science, vol. 2, pp. 273–283, 1989.
  • [33] S. A. Baum, “The MLS problem and its applications in combinatorial optimization,” Journal of Mathematical Programming, vol. 31, no. 5, pp. 10–26, 2005.
  • [34] D. Rosenkrantz and M. Davis, “Search algorithms for finding minimum spanning trees in graphs,” SIAM Journal on Computing, vol. 11, no. 4, pp. 442–456, 1987.
  • [35] M. Roussopoulos, “Minimal separators and lexicographic search,” Journal of Graph Algorithms and Applications, vol. 5, no. 2, pp. 341–364, 1995.
  • [36] M. Krentel, “The complexity of search algorithms in non-chordal graphs,” Computational Complexity Review, vol. 18, no. 2, pp. 41–52, 2004.
  • [37] J. L. Lassez, “Algorithmic strategies for graph search,” Combinatorial Algorithms, vol. 9, no. 1, pp. 125–140, 2006.
  • [38] M. Klotz and B. Z. Chen, “An analysis of LexBFS on arbitrary graphs,” Journal of Computational Algorithms, vol. 12, no. 1, pp. 69–81, 1997.
  • [39] K. Stehlik and D. H. Leigh, “New insights on search and termination algorithms in graphs,” Graph Theory and Applications, pp. 234–257, 2002.
  • [40] F. Zhou and D. A. Parlett, “Optimization methods for graph searching and decomposition,” Journal of Mathematical Logic, vol. 27, no. 3, pp. 102–123, 2009.
  • [41] M. Siddiqi and R. Lau, “LexBFS in non-chordal graphs and related problems,” SIAM Journal on Discrete Mathematics, vol. 14, no. 2, pp. 122–145, 2009.
  • [42] Y. Xu and T. Ren, “LexBFS and its properties in algorithmic applications,” Journal of Algorithms, vol. 26, no. 4, pp. 153–169, 2014.
  • [43] Y. Nakashima and M. Kishida, “On the complexity of graph decomposition,” Algorithmic Graph Theory, vol. 16, no. 5, pp. 188–200, 1999.
  • [44] D. Hachard and L. Lambin, “LexBFS and applications to graph theory problems,” in Proceedings of the European Conference on Algorithms, pp. 72–91, 2001.
  • [45] G. Rhodes and C. C. H. Chan, “Graph search algorithms and their applications,” Journal of the ACM, vol. 41, no. 1, pp. 100–116, 1998.
  • [46] P. Sanchez, “New results in graph search algorithms for efficient computations,” Computational Mathematics, vol. 13, no. 3, pp. 456–473, 2002.
  • [47] J. Liu and X. Xu, “On the search and decomposition algorithms in chordal graphs,” Mathematics of Operations Research, vol. 22, no. 1, pp. 72–85, 2010.