On certificates and lookahead in dynamic graph problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On certificates and lookahead in dynamic graph problems

Full text

Pdf (1.30 MB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms table of contents

Atlanta, Georgia, United States

Pages: 222 - 231

Year of Publication: 1996

ISBN:0-89871-366-8

Authors

Sanjeev Khanna	Department of Computer Science, Stanford University, Stanford, CA
Rajeev Motwani	Department of Computer Science, Stanford University, Stanford, CA
Randall H. Wilson	Intelligent Systems and Robotics Center, Sandia National Laboratories, Albuquerque, NM

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 16, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Rakesh Agrawal , H. V. Jagadish, Materialization and Incremental Update of Path Information, Proceedings of the Fifth International Conference on Data Engineering, p.374-383, February 06-10, 1989
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	S. Albers. The influence of lookahead in competitive on-line algorithms. Technical Report MPI-i-92-143, Max Planck Institute, Germany, 1993.
	4	Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
	5	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	6	Yang Dai , Hiroshi Imai , Kazuo Iwano , Naoki Katoh, How to Treat Delete Requests in Semi-Online Problems, Proceedings of the 4th International Symposium on Algorithms and Computation, p.48-57, December 15-17, 1993
	7	H. Edelsbrunner, and M. H. Overmars. Batched Dynamic Solutions to Decomposable Searching Problems. Journal of Algorithms, 6:515-542 (1985).
	8	David Eppstein, Offline algorithms for dynamic minimum spanning tree problems, Journal of Algorithms, v.17 n.2, p.237-250, Sept. 1994 [doi>10.1006/jagm.1994.1033]
	9	D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification - A technique for speeding up dynamic graph algorithms. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science (1992), pp. 60-69.
	10	D. Eppstein, Z. Galil, G. F. Italiano, and A. Nissenzweig. Sparsification - A technique for speeding up dynamic graph algorithms. Tech. Rep. RC 19272 (83907), IBM (1993).
	11	G.N. Frederickson. Data Structures for On-line Updating of Minimum Spanning Trees, with Applications. SIAM Journal on Computing, 14:781-798 (1985).
	12	Greg N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, Proceedings of the 32nd annual symposium on Foundations of computer science, p.632-641, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185429]
	13	Zvi Galil , Giuseppe F. Italiano, Fully dynamic algorithms for edge connectivity problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.317-327, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103454]
	14	Eric N. Hanson, A performance analysis of view materialization strategies, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.440-453, May 27-29, 1987, San Francisco, California, United States
	15	L. Hellerstein , P. Klein , R. Wilber, On the time-space complexity of reachability queries for preprocessed graphs, Information Processing Letters, v.35 n.5, p.261-267, Aug. 1990 [doi>10.1016/0020-0190(90)90055-3]
	16	Monika Rauch Henzinger , Valerie King, Randomized dynamic graph algorithms with polylogarithmic time per operation, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.519-527, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225269]
	17	M. R. Henzinger , V. King, Fully dynamic biconnectivity and transitive closure, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.664, October 23-25, 1995
	18	L.S. Homem de Mello and S. Lee (editors). Computer- Aided Mechanical Assembly Planning. Kluwer, 1991.
	19	H. V. Jagadish, A compression technique to materialize transitive closure, ACM Transactions on Database Systems (TODS), v.15 n.4, p.558-598, Dec. 1990 [doi>10.1145/99935.99944]
	20	E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (1994), pp. 394-400.
	21	R. Motwani, V. Saraswat, and E. Torng. Online Scheduling with Lookahead: Multipass Assembly Lines. Report CPS-94-41, Department of Computer Science, Michigan State University, 1994.
	22	M. Rauch. Fully dynamic biconnectivity in graphs. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science (1992), pp. 50-59.
	23	A. Schaeffer and P. Varman. Parallel Batch Update of Minimum Spanning Trees. Technical Report CO MP TR90-140, Rice University, 1990.
	24	Arie Segev , Jooseok Park, Maintaining Materialized Views in Distributed Databases, Proceedings of the Fifth International Conference on Data Engineering, p.262-270, February 06-10, 1989
	25	Oded Shmueli , Alon Itai, Maintenance of views, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
	26	V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 14:354-356 (1969).
	27	J. Westbrook and R.E. Tarjan. Maintaining bridgeconnected and biconnected components on-line. Algorithmica, 7:433-464 (1992).
	28	Randall H. Wilson, On geometric assembly planning, Stanford University, Stanford, CA, 1992
	29	Randall H. Wilson , Jean-Claude Latombe, Geometric reasoning about mechanical assembly, Artificial Intelligence, v.71 n.2, p.371-396, Dec. 1994 [doi>10.1016/0004-3702(94)90048-5]
	30	Jan Dithmar Wolter , Richard A. Volz , Tony C. Woo, On the automatic generation of plans for mechanical assembly, 1988
	31	Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298576]

CITED BY 7

	Dan Halperin , Jean-Claude Latombe , Randall H. Wilson, A general framework for assembly planning: the motion space approach, Proceedings of the fourteenth annual symposium on Computational geometry, p.9-18, June 07-10, 1998, Minneapolis, Minnesota, United States
	Kousha Etessami, Dynamic tree isomorphism via first-order updates to a relational database, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.235-243, June 01-04, 1998, Seattle, Washington, United States
	Zvi Galil , Giuseppe F. Italiano , Neil Sarnak, Fully dynamic planarity testing with applications, Journal of the ACM (JACM), v.46 n.1, p.28-91, Jan. 1999
	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997
	Valerie King , Garry Sagert, A fully dynamic algorithm for maintaining the transitive closure, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.492-498, May 01-04, 1999, Atlanta, Georgia, United States
	Christos D. Zaroliagis, Implementations and experimental studies of dynamic graph algorithms, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Valerie King , Garry Sagert, A fully dynamic algorithm for maintaining the transitive closure, Journal of Computer and System Sciences, v.65 n.1, p.150-167, August 2002