Abstract
Graph-searching algorithms typically assume that a node is given from which the search begins but in many applications it is necessary to search a graph repeatedly until all nodes in the graph have been “visited”. Sometimes a priority function is supplied to guide the choice of node when restarting the search, and sometimes not. We call the nodes from which a search of a graph is (re)started the “delegate” of the nodes found in that repetition of the search and we analyse the properties of the delegate function. We apply the analysis to establishing the correctness of the second stage of the Kosaraju-Sharir algorithm for computing strongly connected components of a graph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data Structures and Algorithms. Addison-Wesley, Reading (1982)
Backhouse, R.C.: Closure algorithms and the star-height problem of regular languages. Ph.D. thesis, University of London (1975). https://spiral.imperial.ac.uk/bitstream/10044/1/22243/2/Backhouse-RC-1976-PhD-Thesis.pdf
Backhouse, R.C., Carré, B.A.: Regular algebra applied to path-finding problems. J. Inst. Math. Appl. 15, 161–186 (1975)
Backhouse, R.C., van der Woude, J.: Demonic operators and monotype factors. Math. Struct. Comput. Sci. 3(4), 417–433 (1993)
Backhouse, R.: Regular algebra applied to language problems. J. Logic Algebraic Program. 66, 71–111 (2006)
Backhouse, R., Doornbos, H., Glück, R., van der Woude, J.: Algorithmic graph theory: an exercise in point-free reasoning (2019). http://www.cs.nott.ac.uk/~pasrb2/MPC/BasicGraphTheory.pdf, Also available online at ResearchGate
Backhouse, R.C., van den Eijnde, J.P.H.W., van Gasteren, A.J.M.: Calculating path algorithms. Sci. Comput. Program. 22(1–2), 3–19 (1994)
Conway, J.H.: Regular Algebra and Finite Machines. Chapman and Hall, London (1971)
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Electrical Engineering and Computer Science Series. MIT Press, Cambridge (1990)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Electrical Engineering and Computer Science Series, 3rd edn. MIT Press, Cambridge (2009)
Doornbos, H., Backhouse, R.: Reductivity. Sci. Comput. Program. 26(1–3), 217–236 (1996)
Freyd, P.J., Ščedrov, A.: Categories. North-Holland, Allegories (1990)
Glück, R.: Algebraic investigation of connected components. In: Höfner, P., Pous, D., Struth, G. (eds.) RAMICS 2017. LNCS, vol. 10226, pp. 109–126. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57418-9_7
Hoogendijk, P., Backhouse, R.C.: Relational programming laws in the tree, list, bag, set hierarchy. Sci. Comput. Program. 22(1–2), 67–105 (1994)
King, D.J., Launchbury, J.: Structuring depth-first search algorithms in Haskell. In: POPL 1995. Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programmming Languages, pp. 344–354 (1995)
Sharir, M.: A strong-connectivity algorithm and its application in data flow analysis. Comput. Math. Appl. 7(1), 67–72 (1981)
Tarjan, R.E.: Depth first search and linear graph algorithms. SIAM J. Comput. 1, 146–160 (1972)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Backhouse, R. (2019). An Analysis of Repeated Graph Search. In: Hutton, G. (eds) Mathematics of Program Construction. MPC 2019. Lecture Notes in Computer Science(), vol 11825. Springer, Cham. https://doi.org/10.1007/978-3-030-33636-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-33636-3_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-33635-6
Online ISBN: 978-3-030-33636-3
eBook Packages: Computer ScienceComputer Science (R0)