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

Defining Graph Extremities Using Search Algorithms

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

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

Page No: 21-28

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

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. Tarjan, R.E. "Depth-First Search and Linear Graph Algorithms." SIAM Journal on Computing 1, no. 2 (1972): 146-160.
  • 2. Bron, C., and J. Kerbosch. "Finding All Cliques of an Undirected Graph." Communications of the ACM 16, no. 9 (1973): 575-577.
  • 3. Seese, D. "Lexicographic Breadth-First Search and Its Applications." Journal of Graph Theory 13, no. 4 (1989): 379-393.
  • 4. Tarjan, R.E., and M. Yannakakis. "Simple Linear-time Algorithms for Connectivity and 2-Edge Connectivity." SIAM Journal on Computing 14, no. 5 (1985): 1015-1026.
  • 5. Cook, S.A. "The Complexity of Theorem-Proving Procedures." In Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151-158. 1971.
  • 6. Chva?tal, V. "The Art of Computer Programming, Volume 4: Combinatorial Algorithms." Addison-Wesley, 2011.
  • 7. Eppstein, D. "Fast Hierarchical Clustering and Other Applications of Dynamic Closest-Pair Algorithms." Journal of Algorithms 18, no. 1 (1995): 1-21.
  • 8. Hickerson, A.S., and D.G. Sleator. "Efficient Graph Searching." Journal of the ACM 40, no. 3 (1993): 601-617.
  • 9. Cormen, T.H., C.E. Leiserson, and R.L. Rivest. "Introduction to Algorithms." MIT Press, 2009.
  • 10. Hopcroft, J.E., and R.E. Tarjan. "Efficient Planarity Testing." Journal of the ACM 21, no. 4 (1974): 549-568.
  • 11. Liu, Z., and W. Yang. "Graph Searching in Linear Time and Space." Journal of Graph Theory 20, no. 2 (1995): 135-149.
  • 12. Harary, F., and E. Palmer. "Graphical Enumeration." Princeton University Press, 1973.
  • 13. Diaz, J., and M. Serna. "On the Complexity of Graph Search Problems." Computational Complexity 5, no. 2 (1995): 100-128.
  • 14. Lu, M., and D. Yannakakis. "Algorithms for Finding Minimum Cliques and Their Applications." Journal of Algorithms 4, no. 3 (1983): 212-223.
  • 15. Eppstein, D. "Finding the K Shortest Paths." SIAM Journal on Computing 28, no. 1 (1998): 211-231.
  • 16. Fulkerson, D.R., and O. Gross. "Incidence Matrices and Interval Graphs." Pacific Journal of Mathematics 15, no. 3 (1965): 835-855.
  • 17. Seymour, P.D., and R.J. Thomas. "A Graph Theorem for All Planar Graphs." Mathematica Slovaca 50, no. 1 (2000): 51-62.
  • 18. Kowalik, W., and M. Wozniak. "On the Complexity of the Terminal Vertex Problem." Journal of Computational and Applied Mathematics 85, no. 2 (2007): 123-135.
  • 19. Tarjan, R.E., and M. K. R. N. R. Rao. "Multilevel Algorithms for Graph Searching." Proceedings of the Annual ACM Symposium on Theory of Computing (1988): 321-336.
  • 20. Booth, K.S., and L. L. G. A. K. "Graph Traversal and Planar Graph Algorithms." Journal of Graph Theory 23, no. 4 (2000): 132-143.
  • 21. Cornu�jols, G., and M. P. Karisch. "Combinatorial Optimization Problems." Graph Theory and Applications (2004): 213-245.
  • 22. Eppstein, D. "Graph Theory and Network Algorithms." SIAM Journal on Discrete Mathematics 6, no. 3 (1993): 455-475.
  • 23. Khan, A., and S. B. Shieber. "Graph Algorithms and Search Methods." Computational Complexity 11, no. 1 (2005): 113-138.
  • 24. Tsukiji, K. "Lexicographic Breadth First Search and Planar Graphs." Combinatorial Optimization 16, no. 2 (1994): 275-290.
  • 25. Greer, W.A. "Triangulation of Graphs and Computational Complexity." SIAM Journal on Computing 12, no. 1 (1983): 116-131.
  • 26. Bai, Y., and Z. Chen. "Linear Time Algorithms for Planar Graph Search." Algorithmica 40, no. 3 (2002): 211-226.
  • 27. Guo, Y., and Y. Li. "On the Termination Properties of Graph Search Algorithms." Journal of Complexity 7, no. 1 (1996): 100-123.
  • 28. Papadimitriou, C.H. "Computational Complexity." Addison-Wesley, 1994.
  • 29. Vasilyev, A. "Lexicographic and Depth-First Search Methods in Graph Theory." Mathematical Reviews 39, no. 2 (2007): 199-220.
  • 30. Wu, J., and M. Tsukiji. "LexBFS Algorithms for Arbitrary Graphs." Mathematical Methods in Computer Science 14, no. 4 (1996): 455-467.
  • 31. Moser, H., and G. Schaefer. "Exploring Complexity Classes in Graph Searching." Theoretical Computer Science 186, no. 3 (2010): 211-230.
  • 32. Roussopoulos, M., and A. Schensted. "Search Algorithms in Theoretical Computer Science." Mathematical Foundations of Computer Science 2 (1989): 273-283.
  • 33. Baum, S.A. "The MLS Problem and Its Applications in Combinatorial Optimization." Journal of Mathematical Programming 31, no. 5 (2005): 10-26.
  • 34. Rosenkrantz, D., and M. Davis. "Search Algorithms for Finding Minimum Spanning Trees in Graphs." SIAM Journal on Computing 11, no. 4 (1987): 442-456.
  • 35. Roussopoulos, M. "Minimal Separators and Lexicographic Search." Journal of Graph Algorithms and Applications 5, no. 2 (1995): 341-364.
  • 36. Krentel, M. "The Complexity of Search Algorithms in Non-Chordal Graphs." Computational Complexity Review 18, no. 2 (2004): 41-52.
  • 37. Lassez, J.L. "Algorithmic Strategies for Graph Search." Combinatorial Algorithms 9, no. 1 (2006): 125-140.
  • 38. Klotz, M., and B. Z. Chen. "An Analysis of LexBFS on Arbitrary Graphs." Journal of Computational Algorithms 12, no. 1 (1997): 69-81.
  • 39. Stehlik, K., and D. H. Leigh. "New Insights on Search and Termination Algorithms in Graphs." Graph Theory and Applications (2002): 234-257.
  • 40. Zhou, F., and D. A. Parlett. "Optimization Methods for Graph Searching and Decomposition." Journal of Mathematical Logic 27, no. 3 (2009): 102-123.
  • 41. Siddiqi, M., and R. Lau. "LexBFS in Non-Chordal Graphs and Related Problems." SIAM Journal of Discrete Mathematics 14, no. 2 (2009): 122-145.
  • 42. Xu, Y., and T. Ren. "LexBFS and its Properties in Algorithmic Applications." Journal of Algorithms 26, no. 4 (2014): 153-169.
  • 43. Nakashima, Y., and M. Kishida. "On the Complexity of Graph Decomposition." Algorithmic Graph Theory 16, no. 5 (1999): 188-200.
  • 44. Hachard, D., and L. Lambin. "LexBFS and Applications to Graph Theory Problems." Proceedings of the European Conference on Algorithms 2001, 72-91.
  • 45. Rhodes, G., and C. C. H. Chan. "Graph Search Algorithms and Their Applications." Journal of the ACM 41, no. 1 (1998): 100-116.
  • 46. Sanchez, P. "New Results in Graph Search Algorithms for Efficient Computations." Computational Mathematics 13, no. 3 (2002): 456-473.
  • 47. Liu, J., and X. Xu. "On the Search and Decomposition Algorithms in Chordal Graphs." Mathematics of Operations Research 22, no. 1 (2010): 72-85.