×

Finding paths and deleting edges in directed acyclic graphs. (English) Zbl 0663.68052

An algorithm for path searching and edge deleting in a directed acyclic graph is presented which realizes each searchpath operation in O(\(\ell)\) time, where \(\ell\) is the length of the achieved path, and any number of delete operations in O(mn) worst-case time, where m is the number of edges and n is the number of nodes. The algorithm requires a data structure of size \(O(n^ 2)\) which can be preprocessed in O(mn) time. This seems to improve previously known algorithms, which however handled the edge insertion problem also.
Reviewer: M.Zimand

MSC:

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading · Zbl 0286.68029
[2] Ausiello, G.; Italiano, G. F., On-line computation of minimal and maximal length paths, 13th IFIP Conf. on System Modelling and Optimization (August 31-September 4, 1987), Tokyo
[3] Even, S.; Gazit, H., Updating distances in dynamic graphs, Methods of Operations Research, 49, 371-387 (1985) · Zbl 0565.05052
[4] Even, S.; Shiloach, Y., An on-line edge deletion problem, J. Assoc. Comput. Mach., 28, 1-4 (1981) · Zbl 0454.68075
[5] Frederickson, G. N., Data structures for on-line updating of minimum spanning trees with applications, SIAM J. Comput., 14, 781-798 (1985) · Zbl 0575.68068
[6] Harary, F., Graph Theory (1972), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[7] Harel, D., On-line maintenance of the connected components of dynamic graphs (1982), Unpublished manuscript
[8] Ibaraki, T.; Katoh, N., On-line computation of transitive closure for graphs, Inform. Process. Lett., 16, 95-97 (1983) · Zbl 0514.68062
[9] Italiano, G. F., Transitive closure for dynamic graphs, Proc. 24th Ann. Allerton Conf. on Communication, Control and Computing, 29-38 (1986)
[10] Italiano, G. F., Amortized efficiency of a path retrieval data structure, Theoret. Comput. Sci., 48, 273-281 (1986) · Zbl 0638.68065
[11] La Poutre, J. A.; Van Leewen, J., Maintenance of Transitive Closures and Transitive Reductions of Graphs, (Tech. Rept. RUU-CS-87-25 (1987), Dept. of Computer Science, Univ. of Utrecht: Dept. of Computer Science, Univ. of Utrecht The Netherlands) · Zbl 0662.68071
[12] Rohnert, H., A dynamization of the all pairs least cost path problem, (Proc. 2nd Ann. Symp. on Theoretical Aspects of Computer Science, Vol. 182 (1985), Springer: Springer Berlin), 279-286, Lecture Notes in Computer Science · Zbl 0568.68050
[13] Sleator, D. D., An \(O\)(nm log n) Algorithm for Maximum Network Flow, (Ph.D. Dissertation, Tech. Rept. STAN-CS-80-831 (1980), Computer Science Dept., Stanford Univ: Computer Science Dept., Stanford Univ Stanford, CA)
[14] Sleator, D. D.; Tarjan, R. E., A data structure for dynamic trees, J. Comput. System Sci., 24, 362-381 (1983) · Zbl 0509.68058
[15] Tamassia, R., A Dynamic Data Structure for Planar Graph Embedding, (Tech. Rept. UILU-ENG-87-2265 (October 1987), Coordinated Science Lab., Univ. of Illinois: Coordinated Science Lab., Univ. of Illinois Urbana-Champaign) · Zbl 0649.68071
[16] Tarjan, R. E., Amortized computational complexity, SIAM J. Alg. Disc. Meth., 6, 306-318 (1985) · Zbl 0599.68046
[17] Tarjan, R. E.; Van Leeuwen, J., Worst-case analysis of set union algorithms, J. Assoc.Comput. Mach., 31, 245-281 (1984) · Zbl 0632.68043
[18] Tsakalidis, A. K., The nearest common ancestor in a dynamic tree, (Proc. 14th Internat. Coil. on Automata, Languages and Programming, Vol. 267 (1987), Springer: Springer Berlin), 489-498, Lecture Notes in Computer Science
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.