Incremental FO(+, <) Maintenance of All-Pairs Shortest Paths for Undirected Graphs after Insertions and Deletions.

@inproceedings{DBLP:conf/icdt/PangRD99,
  author    = {Chaoyi Pang and
               Kotagiri Ramamohanarao and
               Guozhu Dong},
  editor    = {Catriel Beeri and
               Peter Buneman},
  title     = {Incremental {\it FO}(+, $<$) Maintenance of All-Pairs Shortest Paths for Undirected
               Graphs after Insertions and Deletions},
  booktitle = {Database Theory - ICDT '99, 7th International Conference, Jerusalem,
               Israel, January 10-12, 1999, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1540},
  year      = {1999},
  isbn      = {3-540-65452-6},
  pages     = {365-382},
  ee        = {db/conf/icdt/PangRD99.html, http://link.springer.de/link/service/series/0558/bibs/1540/15400365.htm},
  crossref  = {DBLP:conf/icdt/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Online Edition: Springer LINK

References

[1]

Giorgio Ausiello, Giuseppe F. Italiano, Alberto Marchetti-Spaccamela, Umberto Nanni: On-Line Computation of Minimal and Maximal Length Paths. Theor. Comput. Sci. 95(2): 245-261(1992) BibTeX

[2]

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX

[3]

Adam L. Buchsbaum, Paris C. Kanellakis, Jeffrey Scott Vitter: A Data Structure for Arc Insertion and Regular Path Finding. SODA 1990: 22-31 BibTeX

[4]

Hristo Djidjev, Grammati E. Pantziou, Christos D. Zaroliagis: On-line and Dynamic Algorithms for Shorted Path Problems. STACS 1995: 193-204 BibTeX

[5]

Guozhu Dong, Chaoyi Pang: Maintaining Transitive Closure in First Order After Node-Set and Edge-Set Deletions. Inf. Process. Lett. 62(4): 193-199(1997) BibTeX

[6]

Guozhu Dong, Jianwen Su: Space-Bounded FOIES. PODS 1995: 139-150 BibTeX

[7]

Guozhu Dong, Rodney W. Topor: Incremental Evaluation of Datalog Queries. ICDT 1992: 282-296 BibTeX

[8]

Guozhu Dong, Kotagiri Ramamohanarao: Maintaining Constrained Transitive Closure by Conjunctive Queries. DOOD 1997: 35-51 BibTeX

[9]

...

[10]

Esteban Feuerstein, Alberto Marchetti-Spaccamela: Dynamic Algorithms for Shortest Paths in Planar Graphs. WG 1991: 187-197 BibTeX

[11]

Stéphane Grumbach, Jianwen Su: First-order Definability over Constraint Databases. CP 1995: 121-136 BibTeX

[12]

Philip N. Klein, Satish Rao, Monika Rauch Henzinger, Sairam Subramanian: Faster shortest-path algorithms for planar graphs. STOC 1994: 27-37 BibTeX

[13]

...

[14]

Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. PODS 1994: 210-221 BibTeX

[15]

...

[16]

Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255 BibTeX

[17]

Philip M. Spira, A. Pan: On Finding and Updating Spanning Trees and Shortest Paths. SIAM J. Comput. 4(3): 375-380(1975) BibTeX

Referenced by

1. Guozhu Dong, Jianwen Su: Incremental Maintenance of Recursive Views Using Relational Calculus/SQL. SIGMOD Record 29(1): 44-51(2000)