Article

Free access

Incremental algorithms for minimal length paths

Authors:

Giorgio Ausiello,

Giuseppe F. Italiano,

Alberto Marchetti Spaccamela,

Umberto NanniAuthors Info & Claims

SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms

Pages 12 - 21

Published: 01 January 1990 Publication History

PDF eReader

References

[1]

R. Agrawal, A. Borgida, and H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proc. A CM-SIGMOD Int. Conf. on Management of Data, 1989.

Digital Library

Google Scholar

[2]

A. V. Aho, J. E. ttopcroft, and J. D. Ullman, The Design and Analysis of Computer Algoritlims, Addison-Wesley, Reading, MA, 1974.

Digital Library

Google Scholar

[3]

G. Ausiello, A. Marchetti Spaccamela, and U. Nanni, Dynamic maintenance of paths and path expressions in graphs, Proc. ls~ Int. Joint Conf. ISSAC 88 (Int. Syrup. on Symbolic and Algebraic Computation) and AAECC 6 (6th Int. Conf. on Applied Algebra, Algebraic Algorithms and Error Correcting Codes), 1988.

Digital Library

Google Scholar

[4]

M. Burke, and B. G. Ryder, Incremental iterative data flow analysis algorithms, Technical Report LCSR-TR-96, Department of Computer Science, Rutgers University, 1987.

Google Scholar

[5]

M. D. Carrol and B. G. Ryder, Incremental data flow analysis via dominator and attribute updates, Proc. 15th Annual A CM SIGA CT- SIGPLAN Syrup. on Principles of Programming Languages, 1988, 274-284.

Digital Library

Google Scholar

[6]

F. Chin and D. Houk, Algorithms for updating minimum spanning trees, J. CompuL System. Sci. 16 (1978), 333-344.

Google Scholar

[7]

D. Eppstein, G. F. Italiano, R. Tamassia, R. E. Tarjan, J. Westbrook, M. Yung, Maintenance of a minimum spanning forest in a dynamic planar graph, These Proceedings.

Digital Library

Google Scholar

[8]

S. Even, and It. Gazit, Updating distances in dynamic graphs, Methods of Opera~ions Research 49 (1985), 371-387.

Google Scholar

[9]

S. Even, and Y. Shiloach, An on-line edge deletion problem, J. Assoc. Comput. Mach. 28 (1981), 1-4.

Digital Library

Google Scholar

[10]

G. N. Frederickson, Data structures for on-line updating of minimum spanning trees, SIAM J. Compul. 14 (1985), 781-798.

Google Scholar

[11]

G. N. Frederickson and M. A. Srinivas, On-line updating of degree-constrained minimum spanning trees, Proc. 22nd Annual Allerton Conference on Communication, Control and Computing, 1984.

Google Scholar

[12]

M. L. Fredman, and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach. 34 (19873, 596-615.

Digital Library

Google Scholar

[13]

M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP- Completeness, W. H. Freeman, 1979.

Digital Library

Google Scholar

[14]

D. Harel, On-line maintenance of the connected components of dynamic graphs, Unpublished manuscript, 1982.

Google Scholar

[15]

N. Florspool, Incremental generation of LR parsers, Technical Report, Department of Computer Science, University of Victoria, 1988.

Google Scholar

[16]

T. Ibaraki, and N. Katoh, On-line computation of transitive closure for graphs, Inform. Process. Left. 16 (1983), 95-97.

Google Scholar

[17]

G. F. Italiano, Amortized efficiency of a path retrieval data structure, Theoret. CompuL Sci. 48 (1986), 273-281.

Digital Library

Google Scholar

[18]

G. F. Italiano, Finding paths and deleting edges in directed aeyclic graphs, Inform. Process. Lelt. 28 (1988), 5-11.

Digital Library

Google Scholar

[19]

H. V. Jagadish, A compression technique to materialize transitive closure, A CM Trans. on Database Systems, to appear.

Digital Library

Google Scholar

[20]

3. A. La Poutr6, and J. van Leeuwen, Maintenance of transitive closure and transitive reduction of graphs, Proc. Workshop on Graph- Theoretic Concepts in Computer Science, 1988, 106-120.

Digital Library

Google Scholar

[21]

E. L. Lawler, Combinatorial optimization: networks and malroids, Holt, Rinehart and Winston, 1976.

Google Scholar

[22]

F. P. Preparata, and R. Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures, Proc. 29th Annual Syrup. on Foundations of Computer Science, 1988, 558-567.

Google Scholar

[23]

J. H. Reif, A topological approach to dynamic graph connectivity, Inform. Process. Left. 25 (1987), 65-70.

Digital Library

Google Scholar

[24]

It. Rohnert, A dynamization of the all pairs least cost path problem, Proc. 2nd Annual Syrup. on Theoretical Aspects of Computer Science, 1985, 279-286.

Digital Library

Google Scholar

[25]

D. D. Sleator, and R. E. Tarjan, A data structure for dynamic trees, J. Comput. System Sci. 24 (1983), 362-381.

Digital Library

Google Scholar

[26]

P. M. Spira and A. Pan, On finding and updating spanning trees and shortest paths, SIAM J. CompuL 4 (1975), 375-380.

Google Scholar

[27]

R. E. Tarjan, Data structures and network algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, SIAM, 1983.

Digital Library

Google Scholar

[28]

R. E. Tarjan, Amortized computational complexity, SIAM J. AIg. Disc. Meth. 6 (1985), 306-318.

Google Scholar

[29]

D. M. Yellin, A dynamic transitive closure algorithm, Research Report, IBM Research Division, T. J. Watson Research Center, 1988.

Google Scholar

[30]

D. M. Yellin, and R. Strom, INC: a tanguage for incremental computations, Proc. A CM SIG- PLAN '88 Conf. on Programming Language Design and implementation, 1988, 115-124.

Digital Library

Google Scholar

Cited By

View all

Mao XMohar BShinkar IO'Donnell R(2024)Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649695(1141-1152)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649695
Heggernes PMancini F(2009)Dynamically maintaining split graphsDiscrete Applied Mathematics10.1016/j.dam.2008.06.028157:9(2057-2069)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.dam.2008.06.028
Yasmin NMenezes R(2006)Incremental computation of shortest paths in semi-dynamic graphs using software componentsProceedings of the 44th annual ACM Southeast Conference10.1145/1185448.1185470(96-101)Online publication date: 10-Mar-2006
https://dl.acm.org/doi/10.1145/1185448.1185470
Show More Cited By

Index Terms

Recommendations

Combinatorial algorithms for listing paths in minimal change order
CAAN'07: Proceedings of the 4th conference on Combinatorial and algorithmic aspects of networking

Combinatorial algorithms that list combinatorial objects in minimal change order are of fundamental interest in computer science and mathematics. In minimal change ordering, successive elements differ in some pre-specified small way. In this paper, we ...
Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want ...
Symmetric Schröder paths and restricted involutions

Let A"k be the set of permutations in the symmetric group S"k with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns A"k. We present a bijection between symmetric Schroder paths of length 2n and involutions of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms

January 1990

522 pages

ISBN:0898712513

Chairman:
David Johnson

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1990

Check for updates

Qualifiers

Article

Conference

SODA90

Sponsor:

SIGACT

SODA90: ACM/SIGACT-SIAM Symposium on Discrete Algorithm

January 22 - 24, 1990

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
770
Total Downloads

Downloads (Last 12 months)80
Downloads (Last 6 weeks)28

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mao XMohar BShinkar IO'Donnell R(2024)Fully Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649695(1141-1152)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649695
Heggernes PMancini F(2009)Dynamically maintaining split graphsDiscrete Applied Mathematics10.1016/j.dam.2008.06.028157:9(2057-2069)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.dam.2008.06.028
Yasmin NMenezes R(2006)Incremental computation of shortest paths in semi-dynamic graphs using software componentsProceedings of the 44th annual ACM Southeast Conference10.1145/1185448.1185470(96-101)Online publication date: 10-Mar-2006
https://dl.acm.org/doi/10.1145/1185448.1185470
Jung SPramanik S(2002)An Efficient Path Computation Model for Hierarchically Structured Topographical Road MapsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2002.103377214:5(1029-1046)Online publication date: 1-Sep-2002
https://dl.acm.org/doi/10.1109/TKDE.2002.1033772
King V(1999)Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in DigraphsProceedings of the 40th Annual Symposium on Foundations of Computer Science10.5555/795665.796487Online publication date: 17-Oct-1999
https://dl.acm.org/doi/10.5555/795665.796487
Cohen RTamassia RAggarwal A(1991)Dynamic expression trees and their applicationsProceedings of the second annual ACM-SIAM symposium on Discrete algorithms10.5555/127787.127805(52-61)Online publication date: 1-Mar-1991
https://dl.acm.org/doi/10.5555/127787.127805
Eppstein DItaliano GTamassia RTarjan RWestbrook JYung MJohnson D(1990)Maintenance of a minimum spanning forest in a dynamic planar graphProceedings of the first annual ACM-SIAM symposium on Discrete algorithms10.5555/320176.320177(1-11)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.5555/320176.320177

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Combinatorial algorithms for listing paths in minimal change order

Improved algorithms for the k simple shortest paths and the replacement paths problems

Symmetric Schröder paths and restricted involutions