Papers on dynamic graph algorithms and related topics.
Collected by G.F. Italiano and D. Eppstein, 1992 - 1995.

@STRING{jgt	= {J. Graph Th.}
       }
@STRING{tcs	= {Theor. Comput. Sci.}
       }
@STRING{jacm	= {J. Assoc. Comput. Mach.}
       }
@STRING{iandc	= {Inf. \& Comput.}
       }
@STRING{sicomp	= {SIAM J. Comput.}
       }
@STRING{mst	= {Math. Syst. Th.}
       }
@STRING{ipl	= {Inform. Proc. Lett.}
       }
@STRING{algs    = {J. Algorithms}
       }
@STRING{algo    = {Algorithmica}
       }
@STRING{jcss    = {J. Comp. Syst. Sci.}
       }
@STRING{cacm    = {Comm. Assoc. Comput. Mach.}
       }
@STRING{acta    = {Acta Informatica}
       }
@STRING{ieeecom = {IEEE Trans. on Commun.}
       }
@STRING{dcg	= {Discrete Comput. Geom.}
       }
@STRING{ojc	= {ORSA J. Comput.}
       }
@STRING{cgta	= {Comput. Geom.: Theory \& Appl.}
       }
@STRING{ijcga	= {Int. J. Comput. Geom. \& Appl.}
       }
@STRING{jsl	= {J. Symbolic Logic}
       }

@ARTICLE(A28,
  AUTHOR = "W. Ackermann",
  TITLE = "Zum {Hilbertshen} Aufbau der reelen Zahlen",
  JOURNAL = "Math. Ann.",
  VOLUME = "99",
  YEAR = "1928",
  PAGES = "118--133")

@ARTICLE(AESW90,
  AUTHOR = "P. K. Agarwal and H. Edelsbrunner and O. Schwarzkopf and E. Welzl",
  TITLE = "Euclidean minimum spanning trees and bichromatic closest pairs",
  JOURNAL = dcg,
  VOLUME = "6",
  YEAR = "1991",
  PAGES = "407--422",
  NOTE = "See also {\em 6th Symp. Comp. Geom.}, 1990, pp. 203--210")

@INPROCEEDINGS(AEM92,
  AUTHOR = "P. K. Agarwal and D. Eppstein and J. Matou\v{s}ek",
  TITLE = "Dynamic algorithms for half-space reporting, proximity
		problems, and geometric minimum spanning trees",
  BOOKTITLE = "Proc. 33rd IEEE Symp. Foundations of Computer Science",
  YEAR = "1992",
  PAGES = "80--89")

@ARTICLE(AIKS91,
  AUTHOR = "P. K. Agarwal and H. Imai and N. Katoh and S. Suri",
  TITLE = "Finding {$k$} points with minimum diameter and related problems",
  JOURNAL = algs,
  VOLUME = "12",
  YEAR = "1991",
  PAGES = "38--56")

@INPROCEEDINGS(AvK93,
  AUTHOR = "P. K. Agarwal and M. {van Kreveld}",
  TITLE = "Connected component and simple polygon intersection searching",
  BOOKTITLE = "Proc. 3rd Worksh. Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 709, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "36--47")

@INPROCEEDINGS(AM92,
  AUTHOR = "P. K. Agarwal and J. Matou\v{s}ek",
  TITLE = "Ray shooting and parametric search",
  BOOKTITLE = "Proc. 24th ACM Symp. Theory of Computing",
  YEAR = "1992",
  PAGES = "517--526")

@ARTICLE(AMS91,
  AUTHOR = "P. K. Agarwal and J. Matou\v{s}ek and S. Suri",
  TITLE = "Farthest neighbors, maximum spanning trees, and related problems
	   in higher dimensions",
  JOURNAL = cgta,
  VOLUME = 4,
  YEAR = 1992,
  PAGES = "189--201",
  NOTE = "See also {\em 2nd Worksh. Algorithms and Data Structures},
	  1991, pp. 105--116")

@ARTICLE(AS91,
  AUTHOR = "P. K. Agarwal and M. Sharir",
  TITLE = "Off-line dynamic maintenance of the width of a planar point set",
  JOURNAL = cgta,
  VOLUME = "1",
  YEAR = "1991",
  PAGES = "65--78")

@ARTICLE(AGSS87,
  AUTHOR = "A. Aggarwal and L. J. Guibas and J. Saxe and P. W. Shor",
  TITLE = "A linear time algorithm for computing
	   the {Voronoi} diagram of a convex polygon",
  JOURNAL = dcg,
  YEAR = "1989",
  PAGES = "591--604",
  NOTE = "See also {\em 19th ACM Symp. Theory of Computing}, 1987, pp. 39--47")

@INPROCEEDINGS(ABJ89,
  AUTHOR = "R. Agrawal and A. Borgida and H. V. Jagadish",
  TITLE = "Efficient management of transitive relationships in large
          data and knowledge bases",
  BOOKTITLE = "Proc. ACM-SIGMOD Int. Conf. on Management of Data",
  YEAR = "1989")

@ARTICLE(AGU,
  AUTHOR = "A. V. Aho and M. R. Garey and J. D. Ullman",
  TITLE = "The transitive reduction of a directed graph",
  JOURNAL = sicomp,
  VOLUME = "1",
  YEAR = "1972",
  PAGES = "131--137")

@BOOK(AMO93,
  AUTHOR = "R. K. Ahuja and T. L. Magnanti and J. B. Orlin",
  TITLE = "Network Flows: Theory, Algorithms, and Applications",
  PUBLISHER = "Prentice Hall",
  YEAR = "1993")

@ARTICLE(AOT89,
  AUTHOR = "R. K. Ahuja and J. B. Orlin and R. E. Tarjan",
  TITLE = "Improved time bounds for the maximum flow problem",
  JOURNAL = sicomp,
  VOLUME = "18",
  YEAR = "1989",
  PAGES = "939--954")

@ARTICLE(AF88,
  AUTHOR = "M. Ajtai and R. Fagin",
  TITLE = "Reachability is harder for directed than for undirected graphs",
  JOURNAL = jsl,
  VOLUME = "55",
  YEAR = "1990",
  PAGES = "113--150",
  NOTE = "See also {\em 29th IEEE Symp. Foundations of Computer Science},
	  1988, pp. 358--367")

@BOOK(AHU74,
  AUTHOR = "A. V. Aho and J. E. Hopcroft and J. D. Ullman",
  TITLE = "The Design and Analysis of Computer Algorithms",
  PUBLISHER = "Addison-Wesley, Reading, MA",
  YEAR = "1974")

@ARTICLE(A90,
  AUTHOR = "N. Alon",
  TITLE = "Generating pseudo-random permutations and maximum flow algorithms",
  JOURNAL = ipl,
  VOLUME = 35,
  YEAR = 1990,
  PAGES = "201--204")

@INPROCEEDINGS(AST90,
  AUTHOR = "N. Alon and P. Seymour and R. Thomas",
  TITLE = "A separator theorem for graphs with an excluded minor
	   and its applications",
  BOOKTITLE = "Proc. 22nd ACM Symp. Theory of Computing",
  YEAR = "1990",
  PAGES = "293--299")

@INPROCEEDINGS(AR92,
  AUTHOR = "G. Albers and T. Roos",
  TITLE = "Voronoi diagrams of moving points in higher dimensional spaces",
  BOOKTITLE = "Proc. 3rd Scandinavian Workshop on Algorithm Theory",
  PUBLISHER = "Lecture Notes in Computer Science 621, Springer-Verlag, Berlin",
  YEAR = "1992",
  PAGES = "399--409")

@INPROCEEDINGS(ACI96,
  AUTHOR = "D. Alberts and G. Cattaneo and G. F. Italiano",
  TITLE = "An empirical study of dynamic graph algorithms",
  BOOKTITLE = "Proc. 7th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = 1996,
  PAGES = "192--201")

@INPROCEEDINGS(AR95,
  AUTHOR = "D. Alberts and M. Rauch Henzinger",
  TITLE = "Average case analysis of dynamic graph algorithms",
  BOOKTITLE = "Proc. 6th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = 1995,
  PAGES = "312--321")

@INPROCEEDINGS(ALMM93,
  AUTHOR = "P. Alimonti and S. Leonardi and A. Marchetti-Spaccamela and
	    X. Messeguer",
  TITLE = "Average Case Analysis of Fully Dynamic Connectivity for
	   Directed Graphs",
  BOOKTITLE = "Proc. Workshop on Graph-Theoretic Concepts in Computer Science",
  YEAR = "1993",
  PAGES = "?")

@INPROCEEDINGS(AH90,
  AUTHOR = "B. Alpern and R. Hoover and B. Rosen and P. Sweeney and F.
           K. Zadeck",
  TITLE = "Incremental evaluation of computational circuits",
  BOOKTITLE = "Proc. 1st ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1990",
  PAGES = "32--42")

@ARTICLE(A93,
  AUTHOR = "N. Amenta",
  TITLE = "Helly theorems and generalized linear programming",
  JOURNAL = dcg,
  VOLUME = 12,
  YEAR = 1994,
  PAGES = "241--261",
  NOTE = "See also {\em 9th Symp. Comp. Geom.}, 1993, pp. 63--72")

@ARTICLE(A70a,
  AUTHOR = "E. M. Andreev",
  TITLE = "On convex polyhedra in {Lobacevskii} space",
  JOURNAL = "Math. USR Sbornik",
  VOLUME = "10(3)",
  YEAR = "1970",
  PAGES = "413--440")

@ARTICLE(A70b,
  AUTHOR = "E. M. Andreev",
  TITLE = "On convex polyhedra of finite volume in {Lobacevskii} space",
  JOURNAL = "Math. USR Sbornik",
  VOLUME = "12(2)",
  YEAR = "1970",
  PAGES = "259--270")

@INPROCEEDINGS(AIIT90,
  AUTHOR = "H. Aonuma and H. Imai and K. Imai and T. Tokuyama",
  TITLE = "Maximin location of convex objects in a polygon
	   and related dynamic {Voronoi} diagrams",
  BOOKTITLE = "Proc. 6th ACM Symp. Computational Geometry",
  YEAR = "1990",
  PAGES = "225--234")

@INPROCEEDINGS(AR93,
  AUTHOR = "D. Armon and J. Reif",
  TITLE = "A dynamic separator algorithm",
  BOOKTITLE = "Proc. 3rd Worksh. Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 709, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "107--118")

@INPROCEEDINGS(ABKY88,
  AUTHOR = "T. Asano and B. Bhattacharya and M. Keil and F. Yao",
  TITLE = "Clustering algorithms based on minimum and maximum spanning trees",
  BOOKTITLE = "Proc. 4th ACM Symp. Computational Geometry",
  YEAR = "1988",
  PAGES = "252--257")

@ARTICLE(At85,
  AUTHOR = "M. Atallah",
  TITLE = "Some dynamic computational geometry problems",
  JOURNAL = "Computers and Mathematics with Applications",
  VOLUME = "11",
  YEAR = "1985",
  PAGES = "1171--1181")

@ARTICLE(AI91,
  AUTHOR = "G. Ausiello and G. F. Italiano",
  TITLE = "On-line algorithms for polynomially solvable satisfiability
          problems",
  JOURNAL = "J. Logic Programming",
  VOLUME = "10",
  NUMBER ="1",
  YEAR = "1991",
  PAGES = "69--90")

@ARTICLE(AIMN90,
  AUTHOR = "G. Ausiello and G. F. Italiano and A. {Marchetti Spaccamela} and
           U. Nanni",
  TITLE = "Incremental algorithms for minimal length paths",
  JOURNAL = algs,
  VOLUME = "12",
  YEAR = "1991",
  PAGES = "615--638")

@ARTICLE(AIMN92,
  AUTHOR = "G. Ausiello and G. F. Italiano and
	    A. {Marchetti Spaccamela} and U. Nanni",
  TITLE = "On-line computation of minimal and maximal length paths",
  JOURNAL = tcs,
  YEAR = "1992",
  VOLUME = "95",
  PAGES = "245--261")

@INPROCEEDINGS(AMN88,
  AUTHOR = "G. Ausiello and A. {Marchetti Spaccamela} and U. Nanni",
  TITLE = "Dynamic maintenance of paths and path expressions in graphs",
  BOOKTITLE = "Proc. Int. Symp. Symbolic and Algebraic Computation",
  PUBLISHER = "Lecture Notes in Computer Science 358, Springer-Verlag, Berlin",
  YEAR = "1989",
  PAGES = "1--12")

@INPROCEEDINGS(ABK92,
  AUTHOR = "Y. Azar and A. Broder and A. Karlin",
  TITLE = "On-line load balancing",
  BOOKTITLE = "Proc. 33rd IEEE Symp. Foundations of Computer Science",
  YEAR = "1992",
  PAGES = "218--225")

@INPROCEEDINGS(ABM93,
  AUTHOR = "Y. Azar and A. Z. Broder and M. S. Manasse",
  TITLE = "On-line choice of on-line algorithms",
  BOOKTITLE = "Proc. 4th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1993",
  PAGES = "432--440")

@INPROCEEDINGS(ANR92,
  AUTHOR = "Y. Azar and J. Naor and R. Rom",
  TITLE = "The competitiveness of online assignments",
  BOOKTITLE = "Proc. 3rd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1992",
  PAGES = "203--210")

@INPROCEEDINGS(BCR88,
  AUTHOR = "R. A. Baeza-Yates and J. C. Culberson and G. J. E. Rawlins",
  TITLE = "Searching with uncertainty",
  BOOKTITLE = "Proc. 1st Scandinavian Workshop on Algorithm Theory",
  PUBLISHER = "Lecture Notes in Computer Science 318, Springer-Verlag, Berlin",
  YEAR = "1988",
  PAGES = "176--189")

@ARTICLE(B80,
  AUTHOR = "L. Banachowski",
  TITLE = "A complement to {Tarjan}'s result about the lower bound on the
          complexity of the set union problem",
  JOURNAL = ipl,
  VOLUME = "11",
  YEAR = "1980",
  PAGES = "59--65")

@ARTICLE(BMN92,
  AUTHOR = "A. Bar-Noy and R. Motwani and J. Naor",
  TITLE = "The greedy algorithm is optimal for online edge coloring",
  JOURNAL = ipl,
  VOLUME = "44",
  YEAR = "1992",
  PAGES = "251--253")

@INPROCEEDINGS(BS91,
  AUTHOR = "A. Bar-Noy and B. Schieber",
  TITLE = "The {Canadian} traveller problem",
  BOOKTITLE = "Proc. 2nd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1991",
  PAGES = "261--270")

@INPROCEEDINGS(BH93,
  AUTHOR = "M. Barbehenn and S. Hutchinson",
  TITLE = "Efficient search and hierarchical motion planning using
	   dynamic single-source shortest paths trees",
  BOOKTITLE = "Proc. IEEE Int. Conf. Robotics and Automation",
  YEAR = 1993,
  PAGES = "566--571")

@ARTICLE(BJM92,
  AUTHOR = "H. Baumgarten and H. Jung and K. Mehlhorn",
  TITLE = "Dynamic point location in general subdivisions",
  JOURNAL = algs,
  VOLUME = 17,
  YEAR = 1994,
  PAGES = "342--380",
  NOTE = "See also {\em 3rd Symp. Discrete Algorithms}, 1992, pp. 250--258")

@ARTICLE(B76,
  AUTHOR = "D. Bean",
  TITLE = "Effective coloration",
  JOURNAL = jsl,
  VOLUME = "41",
  YEAR = "1976",
  PAGES = "469--480")

@ARTICLE(BG91,
  AUTHOR = "R. Beigel and W. I. Gasarch",
  TITLE = "The mapmaker's dilemma",
  JOURNAL = "Discrete Applied Mathematics",
  VOLUME = "34",
  YEAR = "1991",
  PAGES = "37--48")

@INPROCEEDINGS(BBKTW90,
  AUTHOR = "S. {Ben-David} and A. Borodin and R. Karp
	    and G. Tardos and A. Wigderson",
  TITLE = "On the power of randomization in online algorithms",
  BOOKTITLE = "Proc. 22nd ACM Symp. Theory of Computing",
  YEAR = "1990",
  PAGES = "379--386")

@INPROCEEDINGS(B90,
  AUTHOR = "J. L. Bentley",
  TITLE = "Experiments on traveling salesman heuristics",
  BOOKTITLE = "Proc. 1st ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1990",
  PAGES = "91--99")

@ARTICLE(B93,
  AUTHOR = "J. L. Bentley",
  TITLE = "Fast algorithms for geometric traveling salesman problems",
  JOURNAL = ojc,
  VOLUME = "4",
  YEAR = "1992",
  PAGES = "387--411")

@ARTICLE(BeOt79,
  AUTHOR = "J. L. Bentley and T. Ottman",
  TITLE = "Algorithms for reporting and counting geometric intersections",
  JOURNAL = "IEEE Trans. on Computing",
  VOLUME = "C-28",
  YEAR = "1979",
  PAGES = "643--647")

@ARTICLE(BS80,
  AUTHOR = "J. L. Bentley and J. Saxe",
  TITLE = "Decomposable searching problems {I}:
	   static-to-dynamic transformation",
  JOURNAL = algs,
  VOLUME = "1",
  YEAR = "1980",
  PAGES = "301--358")

@ARTICLE(BWY80,
  AUTHOR = "J. L. Bentley and B. W. Weide and A. C. Yao",
  TITLE = "Optimal expected-time algorithms for closest-point problems",
  JOURNAL = "ACM Trans. Math. Softw.",
  VOLUME = "6",
  YEAR = "1980",
  PAGES = "563--580")

@ARTICLE(BPR90,
  AUTHOR = "A. M. Berman and M. C. Paull and B. G. Ryder",
  TITLE  = "Proving relative lower bounds for incremental algorithms",
  JOURNAL = acta,
  VOLUME = "27",
  YEAR = "1990",
  PAGES = "665--683")

@ARTICLE(BM88,
  AUTHOR = "D. Bienstock and C. Monma",
  TITLE = "On the complexity of covering vertices by faces in a planar graph",
  JOURNAL = sicomp,
  VOLUME = "17",
  YEAR = "1988",
  PAGES = "53--76")

@INCOLLECTION(Big90,
  AUTHOR = "N. L. Biggs",
  TITLE = "Some heuristics for graph colouring",
  BOOKTITLE = "Graph Colourings",
  EDITOR = "R. Nelson and R. J. Wilson",
  PUBLISHER = "Pitman Research Notes in Mathematics 218",
  YEAR = "1990",
  PAGES = "87--96")

@ARTICLE(Bi79,
  AUTHOR = "G. Birkhoff",
  TITLE = "Lattice Theory",
  JOURNAL = "American Mathematical Society Colloquium Publications",
  VOLUME = "25", 
  YEAR = "1979")

@ARTICLE(B86,
  AUTHOR = "N. Blum",
  TITLE = "On the single operation worst-case time complexity of the
          disjoint set union problem",
  JOURNAL = sicomp,
  VOLUME = "15",
  YEAR = "1986",
  PAGES = "1021--1024")

@INPROCEEDINGS(Bl90,
  AUTHOR = "A. Blum",
  TITLE = "Some tools for approximate 3-coloring",
  BOOKTITLE = "Proc. 31st IEEE Symp. Foundations of Computer Science",
  YEAR = "1990",
  PAGES = "554--562")

@ARTICLE(Bo92,
  AUTHOR = "R. Board",
  TITLE = "The online graph bandwidth problem",
  JOURNAL = iandc,
  VOLUME = "100",
  YEAR = "1992",
  PAGES = "178--201")

@ARTICLE(Bodl91,
  AUTHOR = "H. L. Bodlaender",
  TITLE = "On the complexity of some coloring games",
  JOURNAL = "Int. J. Foundations of Computer Science",
  VOLUME = "2",
  YEAR = "1991",
  PAGES = "133--147")

@INPROCEEDINGS(Bodl92,
  AUTHOR = "H. L. Bodlaender",
  TITLE = "Kayles on special classes of graphs---an application of
	   Sprague-Grundy theory",
  BOOKTITLE = "Proc. 18th Worksh. Graph-Theoretic Concepts in Computer Science",
  PUBLISHER = "Springer-Verlag",
  YEAR = "1993",
  PAGES = "90--102")

@ARTICLE(Bodl93,
  AUTHOR = "H. L. Bodlaender",
  TITLE = "Complexity of path-forming games",
  JOURNAL = tcs,
  VOLUME = "110",
  YEAR = "1993",
  PAGES = "215--245")

@UNPUBLISHED(Bodl93b,
  AUTHOR = "H. L. Bodlaender",
  TITLE = "Dynamic algorithms for graphs with treewidth 2",
  BOOKTITLE = "Proc. Workshop on Graph-Theoretic Concepts in Computer Science",
  YEAR = "1993",
  PAGES = "?")

@ARTICLE(BK92,
  AUTHOR = "H. L. Bodlaender and D. Kratsch",
  TITLE = "The complexity of coloring games on perfect graphs",
  JOURNAL = tcs,
  VOLUME = "106",
  YEAR = "1992",
  PAGES = "309--326")

@ARTICLE(Bol88,
  AUTHOR = "B. Bollob\'{a}s",
  TITLE = "The chromatic number of random graphs",
  JOURNAL = "Combinatorica",
  VOLUME = "8",
  YEAR = "1988",
  PAGES = "49--55")

@ARTICLE(BDT93,
  AUTHOR = "J.-D. Boissonat and O. Devillers and M. Teillaud",
  TITLE = "A semidynamic construction of higher-order {Voronoi} diagrams
	   and its randomized analysis",
  JOURNAL = algo,
  VOLUME = "9",
  YEAR = "1993",
  PAGES = "329--356")

@ARTICLE(BL76,
  AUTHOR = "K. S. Booth and G. S. Lueker",
  TITLE = "Testing for the consecutive ones property, interval graphs,
	   and graph planarity using {PQ-tree} algorithms",
  JOURNAL = jcss,
  VOLUME = "13",
  YEAR = "1976",
  PAGES = "335--379")

@INPROCEEDINGS(BIRS91,
  AUTHOR = "A. Borodin and S. Irani and P. Raghavan and B. Schieber",
  TITLE = "Competitive paging with locality of reference",
  BOOKTITLE = "Proc. 23rd ACM Symp. Theory of Computing",
  YEAR = "1991",
  PAGES = "249--259",
  NOTE = "To appear in J. Comput. Sys. Sci.")

@ARTICLE(B79,
  AUTHOR = "K. Q. Brown",
  TITLE = "Voronoi diagrams from convex hulls",
  JOURNAL = ipl,
  VOLUME = "9",
  YEAR = "1979",
  PAGES = "223--226")

@INPROCEEDINGS(BKV90,
  AUTHOR = "A. L. Buchsbaum and P. C. Kanellakis and J. S. Vitter",
  TITLE = "A data structure for arc insertion and regular path finding",
  BOOKTITLE = "Proc. 1st ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1990",
  PAGES = "22--31")

@INPROCEEDINGS(BGT91,
  AUTHOR = "H. Bunke and T. Glauser and T.-H. Tran",
  TITLE = "Efficient matching of dynamically changing graphs",
  BOOKTITLE = "Theory and Applications of Image Analysis,
	       Selected Papers from the 7th Scandinavian Conference",
  EDITOR = "P. Johansen and S. Olsen",
  PUBLISHER = "World Scientific, Singapore",
  YEAR = "1992",
  PAGES = "110--124")

%TECHREPORT(BR87,
%  AUTHOR = "M. Burke and B. G. Ryder",
%  TITLE = "Incremental iterative data flow analysis algorithms",
%  NUMBER = "LCSR-TR-96",
%  INSTITUTION = "Department of Computer Science, Rutgers University",
%  YEAR = "1987")

@ARTICLE(BR87,
  AUTHOR = "M. Burke and B. G. Ryder",
  TITLE = "A critical analysis of incremental iterative data flow
	   analysis algorithms",
  JOURNAL = "IEEE Trans. Software Engineering",
  VOLUME = "16",
  YEAR = "1990",
  PAGES = "723--728")

@INPROCEEDINGS(BH74,
  AUTHOR = "R. N. Burns and C. E. Haff",
  TITLE = "A ranking problem in graphs",
  BOOKTITLE = "Proc. 5th Southeast Conf. Combinatorics, Graph Theory and Computing",
  YEAR = "1974",
  PAGES = "461--470")

@INPROCEEDINGS(CK93,
  AUTHOR = "P. B. Callahan and S. R. Kosaraju",
  TITLE = "Faster algorithms for some geometric graph problems in higher dimensions",
  BOOKTITLE = "Proc. 4th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1993",
  PAGES = "291--300")

@TECHREPORT(CFM73,
  AUTHOR = "P. M. Camerini and L. Fratta and F. Maffioli",
  TITLE = "The {$k$} shortest spanning trees of a graph",
  NUMBER = "73-10",
  INSTITUTION = "IEEE-LCE Politechnico di Milano, Italy",
  YEAR = "1973")

@ARTICLE(CMMT86,
  AUTHOR = "P. M. Camerini and F. Maffioli and S. Martello and P. Toth",
  TITLE = "Most and least uniform spanning trees",
  JOURNAL = "Discrete Applied Math.",
  VOLUME = 15,
  YEAR = 1986,
  PAGES = "181--187")

@INPROCEEDINGS(CR88,
  AUTHOR = "M. D. Carrol and B. G. Ryder",
  TITLE = "Incremental data flow analysis via dominator and attribute updates",
  BOOKTITLE = "Proc. 15th ACM Symp. Principles of Programming Languages",
  YEAR = "1988",
  PAGES = "274--284")

@UNPUBLISHED(CI95,
  AUTHOR = "G. Cattaneo and G. F. Italiano",
  TITLE = "Average case and empirical study of sparsification",
  YEAR = 1995,
  NOTE = "Manuscript")

@ARTICLE(ChEd92,
  AUTHOR = "B. Chazelle and H. Edelsbrunner",
  TITLE = "An optimal algorithm for intersecting line segments in the plane",
  JOURNAL = jacm,
  VOLUME = "39",
  YEAR = "1992",
  PAGES = "1--54")

@ARTICLE(CCK88,
  AUTHOR = "C. Cheng and I. A. Cimet and S. P. R. Kumar",
  TITLE = "A protocol to maintain a minimum spanning tree in a dynamic
	   topology",
  YEAR = 1988,
  JOURNAL = "Computer Communication Review",
  VOLUME = 18,
  PAGES = "330--337",
  ABSTRACT = "Presents a distributed protocol for updating and maintaining a
     minimum-weight spanning tree (MST) in a network with changing topology.
     The protocol can respond to multiple link/node failures and recoveries
     that can occur at arbitrary times. Given that an arbitrary finite number
     of topological changes occur during a period, the protocol finds the MST
     corresponding to the latest network, within finite time after the last
     change. The message complexity of the protocol is O(m mod E mod +k mod V
     mod ) when k link recoveries and m link failures occur, where mod V mod
     and mod E mod are the total number of nodes and links, respectively.")

@ARTICLE(CJ90,
  AUTHOR = "S. W. Cheng and R. Janardan",
  TITLE = "New results on dynamic planar point location",
  JOURNAL = sicomp,
  VOLUME = 21,
  YEAR = 1992,
  PAGES = "972--999",
  NOTE = "See also {\em 31st Symp. Found. Comp. Sci.}, 1990, pp. 96--105")

@ARTICLE(CT76,
  AUTHOR = "D. Cheriton and R. E. Tarjan",
  TITLE = "Finding minimum spanning trees",
  JOURNAL = sicomp,
  VOLUME = "5",
  YEAR = "1976",
  PAGES = "310--313")

@INPROCEEDINGS(CH89,
  AUTHOR = "J. Cheriyan and T. Hagerup",
  TITLE = "A randomized maximum-flow algorithm",
  BOOKTITLE = "Proc. 30th IEEE Symp. Foundations of Computer Science",
  YEAR = "1989",
  PAGES = "118--128")

@INPROCEEDINGS(CHM90,
  AUTHOR = "J. Cheriyan and T. Hagerup and K. Mehlhorn",
  TITLE = "Can a maximum flow be computed in o(mn) time?",
  BOOKTITLE = "Proc. 17th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science 443, Springer-Verlag, Berlin",
  YEAR = "1990",
  PAGES = "235--248")

@INPROCEEDINGS(CT92,
  AUTHOR = "J. Cheriyan and R. Thurimella",
  TITLE = "Algorithms for parallel $k$-vertex connectivity and
          sparse certificates",
  BOOKTITLE = "Proc. 23rd ACM Symp. Theory of Computing",
  YEAR = "1991",
  PAGES = "391--401")

@ARTICLE(CKT93,
  AUTHOR = "J. Cheriyan and M. Y. Kao and R. Thurimella",
  TITLE = "Scan-first search and sparse certificates---an improved
	   parallel algorithm for $k$-vertex connectivity",
  JOURNAL = sicomp,
  VOLUME = "22",
  YEAR = "1993",
  PAGES = "157--174")

@INPROCEEDINGS(Ch86,
  AUTHOR = "L. P. Chew",
  TITLE = "There is a planar graph almost as good as the complete graph",
  BOOKTITLE = "Proc. 2nd ACM Symp. Computational Geometry",
  YEAR = "1986",
  PAGES = "169--177")

@INPROCEEDINGS(CD85,
  AUTHOR = "L. P. Chew and R. L. Drysdale",
  TITLE = "Voronoi diagrams based on convex distance functions",
  BOOKTITLE = "Proc. 1st ACM Symp. Computational Geometry",
  YEAR = "1985",
  PAGES = "235--244")

@ARTICLE(CH78,
  AUTHOR = "F. Chin and D. Houk",
  TITLE = "Algorithms for updating minimum spanning trees",
  JOURNAL = jcss,
  VOLUME = "16",
  YEAR = "1978",
  PAGES = "333--344")

@ARTICLE(ChT91,
  AUTHOR = "Y.-J. Chiang and R. Tamassia",
  TITLE = "Dynamization of the trapezoid method for planar point location",
  JOURNAL = ijcga,
  VOLUME = 2,
  YEAR = 1992,
  PAGES = "311--333",
  NOTE = "See also {\em 7th Symp. Comp. Geom.}, 1991, pp. 61--70")

@TECHREPORT(Ch76,
  AUTHOR = "N. Christofides",
  TITLE = "Worst-case analysis of a new heuristic
	   for the traveling salesman problem",
  NUMBER = "388",
  INSTITUTION = "GSIA, Carnegie-Mellon University, Pittsburgh",
  YEAR = "1976")

@ARTICLE(ChSl84,
  AUTHOR = "M. Chrobak and M. {\'{S}lusarek}",
  TITLE = "Problem 84-23",
  JOURNAL = algs,
  VOLUME = "5",
  YEAR = "1984",
  PAGES = "588")

@ARTICLE(ChSl88,
  AUTHOR = "M. Chrobak and M. {\'{S}lusarek}",
  TITLE = "On some packing problems related to dynamic storage allocation",
  JOURNAL = "RAIRO Informatique Th\'{e}oretique et Applications",
  VOLUME = "22",
  YEAR = "1988",
  PAGES = "487--499")

@INPROCEEDINGS(Cl84,
  AUTHOR = "K. L. Clarkson",
  TITLE = "Fast expected-time and approximation algorithms
	   for geometric minimum spanning trees",
  BOOKTITLE = "Proc. 16th ACM Symp. Theory of Computing",
  YEAR = "1984",
  PAGES = "342--348")

@INPROCEEDINGS(CS88,
  AUTHOR = "K. L. Clarkson and P. W. Shor",
  TITLE = "Algorithms for diametral pairs and convex hulls
	   that are optimal, randomized, and incremental",
  BOOKTITLE = "Proc. 4th ACM Symp. Computational Geometry",
  YEAR = "1988",
  PAGES = "12--17")

@INPROCEEDINGS(CSTV93,
  AUTHOR = "R. F. Cohen and S. Sairam and R. Tamassia and J. S. Vitter",
  TITLE = "Dynamic algorithms for optimization problems in bounded
	   tree-width graphs",
  BOOKTITLE = "Proc. 3rd Conf. Integer Programming and Combinatorial
	       Optimization",
  YEAR = "1993")

@INPROCEEDINGS(CT91,
  AUTHOR = "R. F. Cohen and R. Tamassia",
  TITLE = "Dynamic expression trees and their applications",
  BOOKTITLE = "Proc. 2nd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1991",
  PAGES = "52--61")

@ARTICLE(Col81,
  AUTHOR = "C. J. Colbourn",
  TITLE = "On testing isomorphism of permutation graphs",
  JOURNAL = "Networks",
  VOLUME = 11,
  YEAR = 1981,
  PAGES = "13--21")

@ARTICLE(CV88,
  AUTHOR = "R. Cole and U. Vishkin",
  TITLE = "The accelerated centroid decomposition technique for optimal
          parallel tree evaluation in logarithmic time",
  JOURNAL = algo,
  VOLUME = "3",
  YEAR = "1988",
  PAGES = "329--346")

@ARTICLE(CPS85,
  AUTHOR = "D. G. Corneil and Y. Perl and L. K. Stewart",
  TITLE = "A linear recognition algorithm for cographs",
  JOURNAL = sicomp,
  VOLUME = 14,
  YEAR = 1985,
  PAGES = "926--934")

@INPROCEEDINGS(DIIK93,
  AUTHOR = "Y. Dai and H. Imai and K. Iwano and N. Katoh",
  TITLE = "How to treat delete requests in semi-online problems",
  BOOKTITLE = "Proc. 4th Int. Symp. Algorithms and Computation",
  PUBLISHER = "Lecture Notes in Computer Science 762, Springer-Verlag, Berlin",
  YEAR = 1993,
  PAGES = "48--57")

@INCOLLECTION(D51,
  AUTHOR = "G. B. Dantzig",
  TITLE = "Application of the simplex method to a transportation problem",
  BOOKTITLE = "Activity Analysis and Production and Allocation",
  EDITOR = "T. C. Koopmans",
  PUBLISHER = "Wiley",
  YEAR = "1951")

@INPROCEEDINGS(DLSS93,
  AUTHOR = "A. Datta and H.-P. Lenhof and C. Schwarz and M. Smid",
  TITLE = "Static and dynamic algorithms for $k$-point clustering problems",
  BOOKTITLE = "Proc. 3rd Worksh. Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 709, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "265--276")

@ARTICLE(D34,
  AUTHOR = "B. N. Delaunay",
  TITLE = "Sur la sphere vide",
  JOURNAL = "Bull. Acad. Sci. USSR VII: Class. Sci. Math.",
  YEAR = "1934",
  PAGES = "793--800")

@INPROCEEDINGS(DP90,
  AUTHOR = "X. Deng and C. Papadimitriou",
  TITLE = "Exploring an unknown graph",
  BOOKTITLE = "Proc. 31st IEEE Symp. Foundations of Computer Science",
  YEAR = "1990",
  PAGES = "355--361")

@INPROCEEDINGS(DKP91,
  AUTHOR = "X. Deng and T. Kameda and C. Papadimitriou",
  TITLE = "How to learn an unknown environment",
  BOOKTITLE = "Proc. 32nd IEEE Symp. Foundations of Computer Science",
  YEAR = "1991",
  PAGES = "298--303")

@ARTICLE(DMT91,
  AUTHOR = "O. Devillers and S. Meiser and M. Teillaud",
  TITLE = "Fully dynamic {Delaunay} triangulation in
	   logarithmic expected time per operation",
  JOURNAL = cgta,
  VOLUME = 2,
  YEAR = 1992,
  PAGES = "55--80",
  NOTE = "See also {\em 2nd Worksh. Algorithms and Data Structures}, 1991, pp. 42--53")

@INPROCEEDINGS(DT89,
  AUTHOR = "G. {Di Battista} and R. Tamassia",
  TITLE = "Incremental planarity testing",
  BOOKTITLE = "Proc. 30th IEEE Symp. Foundations of Computer Science",
  YEAR = "1989",
  PAGES = "436--441")

@INPROCEEDINGS(DT90,
  AUTHOR = "G. {Di Battista} and R. Tamassia",
  TITLE = "On-line graph algorithms with {SPQR}-trees",
  BOOKTITLE = "Proc. 17th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science 443, Springer-Verlag, Berlin",
  YEAR = "1990",
  PAGES = "598-611")

@INPROCEEDINGS(DS87,
  AUTHOR = "P. F. Dietz and D. D. Sleator",
  TITLE = "Two algorithms for maintaining order in a list",
  BOOKTITLE = "Proc. 19th ACM Symp. Theory of Computing",
  YEAR = "1987",
  PAGES = "365--372")

@ARTICLE(D70,
  AUTHOR = "E. A. Dinitz",
  TITLE = "Algorithm for solution of a problem of maximum flow in
	   networks with power estimation",
  JOURNAL = "Sov. Math. Dokl.",
  VOLUME = "11",
  YEAR = "1970",
  PAGES = "1277--1280")

@INPROCEEDINGS(D92,
  AUTHOR = "E. A. Dinitz",
  TITLE = "The 3-edge-components and a structural description of
          all 3-edge-cuts in a graph",
  BOOKTITLE = "Proc. 18th Int. Workshop on Graph-Theoretic Concepts
              in Computer Science",
  PUBLISHER = "Lecture Notes in Computer Science 657, Springer-Verlag, Berlin",
  YEAR = "1992",
  PAGES = "145--157")

@INPROCEEDINGS(D93,
  AUTHOR = "E. A. Dinitz",
  TITLE = "Maintaining the 4-edge-connected components of a graph on-line",
  BOOKTITLE = "Proc. 2nd Israel Symp. Theory of Computing and Systems",
  YEAR = "1993",
  PAGES = "88-99")

@ARTICLE(DKL76,
  AUTHOR = "E. A. Dinitz and A. V. Karzanov and M.V. Lomonosov",
  TITLE = "On the structure of the system of minimal edge cuts in a graph",
  JOURNAL = "Studies in Discrete Optimization",
  YEAR = "1990",
  PAGES = "290--306",
  Note = "In Russian")

@ARTICLE(DRT92,
  AUTHOR = "B. Dixon and M. Rauch and R. E. Tarjan",
  TITLE = "Verification and sensitivity analysis of minimum spanning
trees in linear time",
  JOURNAL = "SIAM J. Comput.",
  YEAR = 1992,
  PAGES = "1184--1192")

@INPROCEEDINGS(DPZ91,
  AUTHOR = "H. N. Djidjev and G. E. Pantziou and C. D. Zaroliagis",
  TITLE = "Computing shortest paths and distances in planar graphs",
  BOOKTITLE = "Proc. 18th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science 510, Springer-Verlag,
              Berlin",
  YEAR = "1991",
  PAGES = "327--338")

@ARTICLE(DFS87,
  AUTHOR = "D. Dobkin and S. J. Friedman and K. J. Supowit",
  TITLE = "Delaunay graphs are almost as good as complete graphs",

  JOURNAL = dcg,
  VOLUME = "5",
  YEAR = "1990",
  PAGES = "399--407",
  NOTE = "See also {\em 28th Symp. Found. Comp. Sci.}, 1987, pp. 20--26")

@ARTICLE(DS89,
  AUTHOR = "D. Dobkin and S. Suri",
  TITLE = "Maintenance of geometric extrema",
  JOURNAL = jacm,
  VOLUME = "38",
  YEAR = "1991",
  PAGES = "275--298",
  NOTE = "See also {\em 30th Symp. Found. Comp. Sci.}, 1989, pp. 488--493")

@ARTICLE(DS95,
  AUTHOR = "G. Dong and J. Su",
  TITLE = "Incremental and decremental evaluation of transitive closure by
     first-order queries",
  JOURNAL = iandc,
  VOLUME = 120,
  YEAR = 1995,
  PAGES = "101--106",
  ABSTRACT = "We study the following problem. Suppose G is a graph and
     TC/sub G/ its transitive closure. If G' is a new graph obtained
     from G by inserting or deleting an edge e/sub i/ can the new
     transitive closure TC/sub G/' be defined in first-order logic using
     G, TC/sub G/, and e? In this paper, we show that the answer is
     positive for (1) acyclic graphs (main result), (2) graphs where the
     vertices of the deleted edge are not in the same strongly connected
     component, and (3) graphs where there exists at most one path
     between each pair of vertices (0-1-path graphs). It is left open
     whether the new transitive closure is definable in first-order
     logic for all graphs. We also consider the first-order on-line
     computation of the dominator relation.")

@INPROCEEDINGS(Dr90,
  AUTHOR = "R. L. Drysdale",
  TITLE = "A practical algorithm for computing the {Delaunay} triangulation
	   for convex distance functions",
  BOOKTITLE = "Proc. 1st ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1990",
  PAGES = "159--168")

@ARTICLE(EGS86,
  AUTHOR = "H. Edelsbrunner and L. J. Guibas and J. Stolfi",
  TITLE = "Optimal point location in a monotone subdivision",
  JOURNAL = sicomp,
  VOLUME = "15",
  YEAR = "1986",
  PAGES = "317--340")

@ARTICLE(EM90,
  AUTHOR = "H. Edelsbrunner and E. P. {M\"ucke}",
  TITLE = "Simulation of Simplicity: A technique to cope with degenerate
	   cases in geometric algorithms",
  JOURNAL = "ACM Trans. Graphics",
  VOLUME = "9",
  YEAR = "1990",
  PAGES = "66--104")

@INPROCEEDINGS(EdSh92,
  AUTHOR = "H. Edelsbrunner and N. R. Shah",
  TITLE = "Incremental topological flipping works for regular triangulations",
  BOOKTITLE = "Proc. 8th ACM Symp. Computational Geometry",
  YEAR = "1992",
  PAGES = "43--52")

@ARTICLE(E60,
  AUTHOR = "J. Edmonds",
  TITLE = "A combinatorial representation for polyhedral surfaces",
  JOURNAL = "Notices Amer. Math. Soc.",
  VOLUME = "7",
  YEAR = "1960",
  PAGES = "646")

@ARTICLE(EK72,
  AUTHOR = "J. Edmonds and R. M. Karp",
  TITLE = "Theoretical improvements in algorithmic efficiency for
	   network flow problems", 
  JOURNAL = jacm,
  VOLUME = "19",
  YEAR = "1972",
  PAGES = "248--264")

@PHDTHESIS(ElGin85,
  AUTHOR = "H. {El Gindy}",
  TITLE = "Hierarchical decomposition of polygon with applications",
  SCHOOL = "McGill University",
  YEAR = "1985")

@ARTICLE(EA81,
  AUTHOR = "H. {El Gindy} and D. Avis",
  TITLE = "A linear algorithm for computing the visibility polygon from a point",
  JOURNAL = algs,
  VOLUME = "2",
  YEAR = "1981",
  PAGES = "186--197")

@INPROCEEDINGS(E89,
  AUTHOR = "C. Elkan",
  TITLE = "A Decision Procedure for Conjunctive Query Disjointness",
  BOOKTITLE = "Proc. ACM Conf. on Principles of Database Systems",
  YEAR = "1989",
  PAGES = "134--139")

@ARTICLE(E77,
  AUTHOR = "P. van Emde Boas",
  TITLE = "Preserving order in a forest in less than logarithmic time
	   and linear space",
  JOURNAL = ipl,
  VOLUME = "6",
  YEAR = "1977",
  PAGES = "80--82")

@ARTICLE(E92-kmst,
  AUTHOR = "D. Eppstein",
  TITLE = "Finding the {$k$} smallest spanning trees",
  JOURNAL = "BIT",
  VOLUME = "32",
  YEAR = "1992",
  PAGES = "237--248")

  NOTE = "See also {\em 2nd Scand. Worksh. Algorithm Th.}, 1990, pp. 38--47")

@ARTICLE(E92-3lp,
  AUTHOR = "D. Eppstein",
  TITLE = "Dynamic three-dimensional linear programming",
  JOURNAL = ojc,
  VOLUME = "4",
  YEAR = "1992",
  PAGES = "360--368",
  NOTE = "See also {\em 32nd Symp. Found. Comp. Sci.}, 1991, pp. 488--494")

@INPROCEEDINGS(E93-rcg,
  AUTHOR = "D. Eppstein",
  TITLE = "Average case analysis of dynamic geometric optimization",
  BOOKTITLE = "Proc. 5th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1994",
  PAGES = "77-86",
  NOTE = "To appear in {\em Computational Geometry Theory \& Applications}")

@INPROCEEDINGS(E93-nsp,
  AUTHOR = "D. Eppstein",
  TITLE = "Clustering for faster network simplex pivots",
  BOOKTITLE = "Proc. 5th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1994",
  PAGES = "160-166")

@ARTICLE(E94-off,
  AUTHOR = "D. Eppstein",
  TITLE = "Offline algorithms for dynamic minimum spanning tree problems",
  JOURNAL = algs,
  VOLUME = 17,
  YEAR = 1994,
  PAGES = "237--250")

  NOTE = "See also {\em 2nd Worksh. Algorithms and Data Structures},
	  1991, pp. 392--399")

@ARTICLE(E94-kmst,
  AUTHOR = "D. Eppstein",
  TITLE = "Tree-weighted neighbors and geometric {$k$} smallest spanning trees",
  JOURNAL = "Int. J. Comput. Geom. \& Appl.",
  YEAR = 1994,
  VOLUME = 4,
  PAGES = "229--238")

@ARTICLE(E95-csg,
  AUTHOR = "D. Eppstein",
  TITLE = "Asymptotic speed-ups in constructive solid geometry",
  JOURNAL = algo,
  VOLUME = 13,
  YEAR = 1995,
  PAGES = "462--471")

@TECHREPORT(E95-mrbc,
  AUTHOR = "D. Eppstein",
  TITLE = "Minimum range balanced cuts via dynamic subset sums",
  NUMBER = "95-10",
  INSTITUTION = "Department of Information and Computer Science,
		 University of California, Irvine",
  YEAR = "1995")

@ARTICLE(E95-mdf,
  AUTHOR = "D. Eppstein",
  TITLE = "Dynamic Euclidean Minimum Spanning Trees and Extrema of Binary Functions",
  JOURNAL = dcg,
  VOLUME = 13,
  YEAR = 1995,
  PAGES = "237--250")

@ARTICLE(EE94,
  AUTHOR = "D. Eppstein and J. Erickson",
  TITLE = "Iterated nearest neighbors and finding minimal polytopes",
  JOURNAL = dcg,
  VOLUME = 11,
  YEAR = 1994,
  PAGES = "321--350",
  NOTE = "See also {\em 4th Symp. Discrete Algorithms}, 1993, pp. 64--73")

@INPROCEEDINGS(EGIN92,
  AUTHOR = "D. Eppstein and Z. Galil and G. F. Italiano and A. Nissenzweig",
  TITLE = "Sparsification -- {A} technique for speeding up dynamic graph
          algorithms",
  BOOKTITLE = "Proc. 33rd IEEE Symp. Foundations of Computer Science",
  YEAR = "1992",
  PAGES = "60--69")

@TECHREPORT(EGI93,
  AUTHOR = "D. Eppstein and Z. Galil and G.F. Italiano",
  TITLE = "Improved Sparsification",
  NUMBER = "93-20",
  INSTITUTION = "Department of Information and Computer Science,
		 University of California, Irvine",
  YEAR = "1993")

@INPROCEEDINGS(EGIS93,
  AUTHOR = "D. Eppstein and Z. Galil and G. F. Italiano and T. H. Spencer",
  TITLE = "Separator based sparsification for dynamic planar graph algorithms",
  BOOKTITLE = "Proc. 25th ACM Symp. Theory of Computing",
  YEAR = "1993",
  PAGES = "208--217")

@ARTICLE(EIT90,
  AUTHOR = "D. Eppstein and G. F. Italiano and R. Tamassia and R. E. Tarjan
           and J. Westbrook and M. Yung",
  TITLE = "Maintenance of a minimum spanning forest in a dynamic plane graph",
  JOURNAL = algs,
  VOLUME = "13",
  YEAR = "1992",
  PAGES = "33--54")

  NOTE = "See also {\em 1st Symp. Discrete Algorithms}, 1990, pp. 1-11")

@INPROCEEDINGS(EMT93,
  AUTHOR = "D. Eppstein and G. L. Miller and S.-H. Teng",
  TITLE = "A deterministic linear time algorithm for geometric
	   separators and its applications",
  BOOKTITLE = "9th ACM Symp. Computational Geometry",
  YEAR = "1993",
  PAGES = "99--108")

@BOOK(E79,
  AUTHOR = "S. Even",
  TITLE = "Graph Algorithms",
  PUBLISHER = "Computer Science Press, Potomac, MD",
  YEAR = "1979")

@ARTICLE(EG85,
  AUTHOR = "S. Even and H. Gazit",
  TITLE = "Updating distances in dynamic graphs",
  JOURNAL = "Methods of Operations Research",
  VOLUME = "49",
  YEAR = "1985",
  PAGES = "371--387")

@ARTICLE(ES81,
  AUTHOR = "S. Even and Y. Shiloach",
  TITLE = "An on-line edge deletion problem",
  JOURNAL = jacm,
  VOLUME = "28",
  YEAR = "1981",
  PAGES = "1--4")

@ARTICLE(ET76,
  AUTHOR = "S. Even and R. E. Tarjan",
  TITLE = "Computing an st-numbering",
  JOURNAL = tcs,
  VOLUME = "2",
  YEAR = "1976",
  PAGES = "339--344")

@INPROCEEDINGS(FM92,
  AUTHOR = "T. Feder and M. Mihail",
  TITLE = "Balanced matroids",
  BOOKTITLE = "Proc. 24th ACM Symp. Theory of Computing",
  YEAR = "1992",
  PAGES = "26--38")

@INPROCEEDINGS(FBS96,
  AUTHOR = "D. Fernandez-Baca and G. Slutzki and D. Eppstein",
  TITLE = "Using sparsification for parametric minimum spanning tree problems",
  BOOKTITLE = "Proc. 5th Scand. Worksh. Algorithm Theory",
  YEAR = 1996,
  NOTE = "To appear")

@INPROCEEDINGS(FM91,
  AUTHOR = "E. Feuerstein and A. {Marchetti Spaccamela}",
  TITLE = "Dynamic algorithms for shortest paths in planar graphs",
  BOOKTITLE = "Proc. 17th Int. Workshop on Graph-theoretic Concepts
              in Computer Science",
  PUBLISHER = "Lecture Notes in Computer Science 570, Springer-Verlag, Berlin",
  YEAR = "1991",
  PAGES = "187--197")

@INPROCEEDINGS(FFKR91,
  AUTHOR = "A. Fiat and D. P. Foster and H. Karloff and Y. Rabani
	    and Y. Ravid and S. Vishwanathan",
  TITLE = "Competitive algorithms for layered graph traversal",
  BOOKTITLE = "Proc. 32nd IEEE Symp. Foundations of Computer Science",
  YEAR = "1991",
  PAGES = "288--297")

@INPROCEEDINGS(FRR90,
  AUTHOR = "A. Fiat and Y. Rabani and Y. Ravid",
  TITLE = "Competitive $k$-server algorithms",
  BOOKTITLE = "Proc. 31st IEEE Symp. Foundations of Computer Science",
  YEAR = "1990",
  PAGES = "454--463")

@INCOLLECTION(F72,
  AUTHOR = "M. J. Fischer",
  TITLE = "Efficiency of equivalence algorithms",
  BOOKTITLE = "Complexity of computer computations",
  EDITOR = "R. E. Miller and J. W. Thatcher",
  PUBLISHER = "Plenum Press, New York",
  YEAR = "1972",
  PAGES = "153--168")

@ARTICLE(FF56,
  AUTHOR = "L. R. {Ford, jr.} and D. R. Fulkerson",
  TITLE = "Maximal flow through a network",
  JOURNAL = "Can. J. Math.",
  VOLUME = "8",
  YEAR = "1956",
  PAGES = "399--404")

@ARTICLE(F87,
  AUTHOR = "S. Fortune",
  TITLE = "A sweepline algorithm for {Voronoi} diagrams",
  JOURNAL = algo,
  VOLUME = "2",
  YEAR = "1987",
  PAGES = "153--174")

@ARTICLE(FIN93,
  AUTHOR = "A. Frank and T. Ibaraki and H. Nagamochi",
  TITLE = "On sparse subgraphs preserving connectivity properties",
  JOURNAL = jgt,
  VOLUME = "17",
  YEAR = "1993",
  PAGES = "275--281")

@ARTICLE(F85,
  AUTHOR = "G. N. Frederickson",
  TITLE ="Data structures for on-line updating of minimum spanning trees",
  JOURNAL = sicomp,
  VOLUME = "14",
  YEAR = "1985",
  PAGES = "781--798")

@ARTICLE(F87-psp,
  AUTHOR = "G. N. Frederickson",
  TITLE = "Fast algorithms for shortest paths in planar graphs,
	   with applications",
  JOURNAL = sicomp,
  VOLUME = "16",
  YEAR = "1987",
  PAGES = "1004--1022")

@ARTICLE(F90-dsp,
  AUTHOR = "G. N. Frederickson",
  TITLE = "A distributed shortest path algorithm for a planar network",
  JOURNAL = iandc,
  VOLUME = "86",
  YEAR = "1990",
  PAGES = "140--159")

@ARTICLE(F91-psp,
  AUTHOR = "G. N. Frederickson",
  TITLE = "Planar graph decomposition and all pairs shortest paths",
  JOURNAL = jacm,
  VOLUME = "38",
  YEAR = "1991",
  PAGES = "162--204")

@INPROCEEDINGS(F91,
  AUTHOR = "G. N. Frederickson",
  TITLE = "Ambivalent data structures for dynamic 2-edge-connectivity and
           $k$ smallest spanning trees",
  BOOKTITLE = "Proc. 32nd Symp. Foundations of Computer Science",
  YEAR = "1991",
  PAGES = "632--641")

@INPROCEEDINGS(F93,
  AUTHOR = "G. N. Frederickson",
  TITLE = "A data structure for dynamically maintaining rooted trees",
  BOOKTITLE = "Proc. 4th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1993",
  PAGES = "175--184")

@ARTICLE(F93-heapsel,
  AUTHOR = "G. N. Frederickson",
  TITLE = "An optimal algorithm for selection in a min-heap",
  JOURNAL = iandc,
  VOLUME = "104",
  YEAR = "1993",
  PAGES = "197--214")

@UNPUBLISHED(F94,
  AUTHOR = "G. N. Frederickson",
  TITLE = "Maintaining regular properties dynamically in $k$-terminal graphs",
  YEAR = "1994",
  NOTE = "Manuscript")

@ARTICLE(FJ89,
  AUTHOR = "G. N. Frederickson and R. Janardan",
  TITLE = "Efficient message routing in planar networks",
  JOURNAL = sicomp,
  VOLUME = "18",
  YEAR = "1989",
  PAGES = "843--857")

@ARTICLE(FS84,
  AUTHOR = "G. N. Frederickson and M. A. Srinivas",
  TITLE = "Data structures for online updating of
	   matroid intersection solutions",
  BOOKTITLE = "Proc. 16th ACM Symp. Theory of Computing",
  YEAR = "1984",
  PAGES = "383--390")

@ARTICLE(FS89,
  AUTHOR = "G. N. Frederickson and M. A. Srinivas",
  TITLE = "Algorithms and data structures for an expanded family of matroid
          intersection problems",
  JOURNAL = sicomp,
  VOLUME = "18",
  YEAR = "1989",
  PAGES = "112--138")

@TECHREPORT(F89,
  AUTHOR = "M. L. Fredman",
  TITLE = "On the cell probe complexity of the set union problem",
  INSTITUTION = "Bell Comunications Research",
  YEAR = "1989",
  NUMBER = "TM-ARH-013-570")

@ARTICLE(FR95,
  AUTHOR = "M. L. Fredman and M. R. Henzinger",		  
  TITLE = "Lower bounds for fully dynamic connectivity problems in
		  graphs",
  JOURNAL = algo,
  NOTE = "To appear")

@INPROCEEDINGS(FS89b,
  AUTHOR = "M. L. Fredman and M. E. Saks",
  TITLE = "The cell probe complexity of dynamic data structures",
  BOOKTITLE = "Proc. 21st ACM Symp. Theory of Computing",
  YEAR = "1989",
  PAGES = "345--354")

@ARTICLE(FT87,
  AUTHOR = "M. L. Fredman and R. E. Tarjan",
  TITLE = "Fibonacci heaps and their uses in improved network optimization
          algorithms",
  JOURNAL = jacm,
  VOLUME = "34",
  YEAR = "1987",
  PAGES = "596--615")

@INPROCEEDINGS(FW90,
  AUTHOR = "M. L. Fredman and D. E. Willard",
  TITLE = "Trans-dichotomous algorithms for minimum spanning trees
           and shortest paths",
  BOOKTITLE = "Proc. 31st IEEE Symp. Foundations of Computer Science",
  YEAR = "1990",
  PAGES = "719--725")

@INPROCEEDINGS(FMT92,
  AUTHOR = "A. M. Frieze and G. L. Miller and S.-H. Teng",
  TITLE = "Separator based parallel divide and conquer in computational
	   geometry",
  BOOKTITLE = "Proc. 4th ACM Symp. Parallel Algorithms and Architectures",
  YEAR = "1992",
  PAGES = "420--430")

@ARTICLE(FL91,
  AUTHOR = "J.-J. Fu and R. C. T. Lee",
  TITLE = "Voronoi diagrams of moving points in the plane",
  JOURNAL = "Int. J. Computational Geometry and Applications",
  VOLUME = "1",
  YEAR = "1991",
  PAGES = "23--32")

@ARTICLE(G77,
  AUTHOR = "H. N. Gabow",
  TITLE = "Two algorithms for generating weighted spanning trees in order",
  JOURNAL = sicomp,
  VOLUME = "6",
  YEAR = "1977",
  PAGES = "139--150")

@INPROCEEDINGS(G85,
  AUTHOR = "H. N. Gabow",
  TITLE = "A scaling algorithm for weighted matching on general graphs",
  BOOKTITLE = "Proc. 26st IEEE Symp. Foundations of Computer Science",
  YEAR = "1985",
  PAGES = "90--100")

@INPROCEEDINGS(G91,
  AUTHOR = "H. N. Gabow",
  TITLE = "A matroid approach to finding edge connectivity
          and packing arborescences",
  BOOKTITLE = "Proc. 23rd ACM Symp. Theory of Computing",
  YEAR = "1991",
  PAGES = "112--122")

@INPROCEEDINGS(G92,
  AUTHOR = "H. N. Gabow",
  TITLE = "Applications of a poset representation to edge connectivity
          and graph rigidity",
  BOOKTITLE = "Proc. 32nd IEEE Symp. Foundations of Computer Science",
  YEAR = "1991",
  PAGES = "812--821")

@INPROCEEDINGS(GBT84,
  AUTHOR = "H. N. Gabow and J. L. Bentley and R. E. Tarjan",
  TITLE = "Scaling and related techniques for geometry problems",
  BOOKTITLE = "Proc. 16th ACM Symp. Theory of Computing",
  YEAR = "1984",
  PAGES = "135--143")

@ARTICLE(GGST86,
  AUTHOR = "H. N. Gabow and Z. Galil and T. Spencer and R. E. Tarjan",
  TITLE = "Efficient algorithms for finding minimum spanning trees
	   in undirected and directed graphs",
  JOURNAL = "Combinatorica",
  VOLUME = "6",
  YEAR = "1986",
  PAGES = "109--122")

@INPROCEEDINGS(GS85,
  AUTHOR = "H. N. Gabow and M. Stallman",
  TITLE = "Efficient algorithms for graphic matroid intersection and parity",
  BOOKTITLE = "Proc. 12th Int. Coll. Automata, Languages, and Programming",
  PUBLISHER = "Lecture Notes in Computer Science 194, Springer-Verlag, Berlin",
  YEAR = "1985",
  PAGES = "210--220")

@ARTICLE(GT85,
  AUTHOR = "H. N. Gabow and R. E. Tarjan",
  TITLE = "A linear-time algorithm for a special case of disjoint set union",
  JOURNAL = jcss,
  VOLUME = "30",
  YEAR = "1985",
  PAGES = "209--221")

@INPROCEEDINGS(GI91stoc,
  AUTHOR = "Z. Galil and G. F. Italiano",
  TITLE = "Fully dynamic algorithms for edge connectivity problems",
  BOOKTITLE = "Proc. 23rd ACM Symp. Theory of Computing",
  YEAR = "1991",
  PAGES = "317--327")

@INPROCEEDINGS(GI91icalp,
  AUTHOR = "Z. Galil and G. F. Italiano",
  TITLE = "Maintaining biconnected components of dynamic planar graphs",
  BOOKTITLE = "Proc. 18th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science 510, Springer-Verlag,
              Berlin",
  YEAR = "1991",
  PAGES = "339--350")

@ARTICLE(GI91sigact,
  AUTHOR = "Z. Galil and G. F. Italiano",
  TITLE = "Reducing edge connectivity to vertex connectivity",
  JOURNAL = "Sigact News",
  VOLUME = "22",
  YEAR = "1991",
  PAGES = "57--61")

@ARTICLE(GI912f,
  AUTHOR = "Z. Galil and G. F. Italiano",
  TITLE = "Fully dynamic algorithms for 2-edge-connectivity",
  JOURNAL = sicomp,
  VOLUME = "21",
  YEAR = "1992",
  PAGES = "1047--1069")

@ARTICLE(GI913s,
  AUTHOR = "Z. Galil and G. F. Italiano",
  TITLE = "Maintaining the 3-edge-connected components of a graph on-line",
  JOURNAL = sicomp,
  VOLUME = "22",
  YEAR = "1993",
  PAGES = "11--28")

@UNPUBLISHED(GI913f,
  AUTHOR = "Z. Galil and G. F. Italiano",
  TITLE = "Fully dynamic algorithms for 3-edge-connectivity",
  NOTE = "Manuscript",
  YEAR = 1991)

@INPROCEEDINGS(GIS92,
  AUTHOR = "Z. Galil and G. F. Italiano and N. Sarnak",
  TITLE = "Fully dynamic planarity testing",
  BOOKTITLE = "Proc. 24th ACM Symp. Theory of Computing",
  YEAR = "1992",
  PAGES = "495--506")

@ARTICLE(GN80,
  AUTHOR = "Z. Galil and A. Naamad",
  TITLE = "An {$O(EV\log^2 V)$} algorithm for the maximal flow problem",
  JOURNAL = jcss,
  VOLUME = 21,
  YEAR = 1980,
  PAGES = "203--217")

@ARTICLE(GS88,
  AUTHOR = "Z. Galil and B. Schieber",
  TITLE = "On finding most uniform spanning trees",
  JOURNAL = "Discrete Applied Math.",
  VOLUME = 20,
  YEAR = 1988,
  PAGES = "173--175")

@ARTICLE(GF64,
  AUTHOR = "B. A. Galler and M. Fischer",
  TITLE = "An improved equivalence algorithm",
  JOURNAL = cacm,
  VOLUME = "7",
  YEAR = "1964",
  PAGES = "301--303")

@BOOK(GJ79,
  AUTHOR = "M. R. Garey and D. S. Johnson",
  TITLE = "Computers and intractability: a guide to the theory of
	   NP-Completeness",
  PUBLISHER = "W. H. Freeman",
  YEAR = "1979")

@INPROCEEDINGS(GI92,
  AUTHOR = "D. Giammarresi and G. F. Italiano",
  TITLE = "Dynamic 2- and 3-connectivity on planar graphs",
  BOOKTITLE = "Proc. 3rd Scandinavian Workshop on Algorithm Theory",
  PUBLISHER = "Lecture Notes in Computer Science 621, Springer-Verlag, Berlin",
  YEAR = "1992",
  PAGES = "221--232")

@ARTICLE(GT88,
  AUTHOR = "A. V. Goldberg and R. E. Tarjan",
  TITLE = "A new approach to the maximum flow problem",
  JOURNAL = jacm,
  VOLUME = "35",
  YEAR = "1988",
  PAGES = "921--940")

@INPROCEEDINGS(GMSS93,
  AUTHOR = "M. Golin and R. Raman and C. Schwarz and M. Smid",
  TITLE = "Randomized data structures for the dynamic closest-pair problem",
  BOOKTITLE = "Proc. 4th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1993",
  PAGES = "301--310")

@BOOK(G80,
  AUTHOR = "M. C. Golumbic",
  TITLE = "Algorithmic Graph Theory and Perfect Graphs",
  PUBLISHER = "Academic Press, San Diego",
  YEAR = "1980")

@INPROCEEDINGS(Goo92,
  AUTHOR = "M. T. Goodrich",
  TITLE = "Planar separators and parallel polygon triangulation",
  BOOKTITLE = "Proc. 24th ACM Symp. Theory of Computing",
  YEAR = "1992",
  PAGES = "507--516")

@INPROCEEDINGS(GT91,
  AUTHOR = "M. T. Goodrich and R. Tamassia",
  TITLE = "Dynamic trees and dynamic point location",
  BOOKTITLE = "Proc. 23rd ACM Symp. Theory of Computing",
  YEAR = "1991",
  PAGES = "523--533")

@ARTICLE(GS78,
  AUTHOR = "S. Goto and A. Sangiovanni-Vincentelli",
  TITLE = "A new shortest path updating algorithm",
  JOURNAL = "Networks",
  YEAR = 1978,
  VOLUME = 8,
  PAGES = "341--372")

@ARTICLE(GM76,
  AUTHOR = "G. R. Grimmett and C. J. H. McDiarmid",
  TITLE = "On colouring random graphs",
  JOURNAL = "Math. Proc. Cambridge Philos. Soc.",
  VOLUME = "77",
  YEAR = "1976",
  PAGES = "313--324")

@ARTICLE(GKS90,
  AUTHOR = "L. J. Guibas and D. E. Knuth and M. Sharir",
  TITLE = "Randomized incremental construction of {Delaunay} and {Voronoi} diagrams",
  JOURNAL = algo,
  VOLUME = "7",
  YEAR = "1992",
  PAGES = "381--413",
  NOTE = "See also {\em 17th Int. Coll. on Automata, Languages and
	  Programming}, 1990, pp. 414--431")

@INPROCEEDINGS(GMR91,
  AUTHOR = "L. Guibas and J. S. B. Mitchell and T. Roos",
  TITLE = "Voronoi diagrams of moving points in the plane",
  BOOKTITLE = "Proc. 17th Int. Workshop on Graph-theoretic Concepts in Computer Science",
  PUBLISHER = "Lecture Notes in Computer Science 570, Springer-Verlag, Berlin",
  YEAR = "1991",
  PAGES = "113--125")

@ARTICLE(GS85b,
  AUTHOR = "L. Guibas and J. Stolfi",
  TITLE = "Primitives for the manipulation of general subdivision and the
         computation of {V}oronoi diagrams",
  JOURNAL = "ACM Trans. on Graphics", 
  VOLUME = "4",
  YEAR = "1985",
  PAGES = "74--123")

@ARTICLE(GL88,
  AUTHOR = "A. {Gy\'{a}rf\'{a}s} and J. Lehel",
  TITLE = "Online and first-fit colorings of graphs",
  JOURNAL = jgt,
  VOLUME = "12",
  YEAR = "1988",
  PAGES = "217--227")

@INPROCEEDINGS(Ha92,
  AUTHOR = "M. M. Halld\'{o}rsson",
  TITLE = "Parallel and on-line graph coloring algorithms",
  BOOKTITLE = "Proc. 3rd Int. Symp. Algorithms and Computation",
  PUBLISHER = "Lecture Notes in Computer Science, Springer-Verlag, Berlin",
  YEAR = "1992",
  PAGES = "61--70")

@ARTICLE(Ha93,
  AUTHOR = "M. M. Halld\'{o}rsson",
  TITLE = "A still better performance guarantee for approximate graph coloring",
  JOURNAL = ipl,
  VOLUME = "45",
  YEAR = "1993",
  PAGES = "19--23")

@INPROCEEDINGS(HS92,
  AUTHOR = "M. H. Halld\'{o}rsson and M. Szegedy",
  TITLE = "Lower bounds on on-line graph coloring",
  BOOKTITLE = "Proc. 3rd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1992",
  PAGES = "211--216")

@ARTICLE(HKRT92,
  AUTHOR = "X. Han and P. Kelsen and V. Ramachandran and R. E. Tarjan",
  TITLE = "Computing minimal spanning subgraphs in linear time",
  JOURNAL = sicomp,
  VOLUME = 24,
  YEAR = 1995,
  PAGES = "1332--1358")

  BOOKTITLE = "Proc. 3rd ACM/SIAM Symp. Discrete Algorithms",
  YEAR = "1992",
  PAGES = "146--156")

@BOOK(H69,
  AUTHOR = "F. Harary",
  TITLE = "Graph Theory",
  PUBLISHER = "Addison-Wesley, Reading, MA",
  YEAR = "1969")

@UNPUBLISHED(H82,
  AUTHOR = "D. Harel",
  TITLE = "On-line maintenance of the connected components of dynamic graphs",
  NOTE = "Unpublished manuscript",
  YEAR = "1982")

@ARTICLE(HT84,
  AUTHOR = "D. Harel and R. E. Tarjan",
  TITLE = "Fast Algorithms for Finding Nearest Common Ancestors", 
  JOURNAL = sicomp,
  YEAR = "1984")

@ARTICLE(Ha81,
  AUTHOR = "R. Hassin",
  TITLE = "Maximum flow in {$(s,t)$}-planar networks",
  JOURNAL = ipl,
  VOLUME = "13",
  YEAR = "1981",
  PAGES = "107")

@ARTICLE(HJ85,
  AUTHOR = "R. Hassin and D. B. Johnson",
  TITLE = "An {$O(n\log^2 n)$} algorithm for maximum flow
	   in undirected planar networks",
  JOURNAL = sicomp,
  VOLUME = "14",
  YEAR = "1985",
  PAGES = "612--624")

@ARTICLE(HK70,
  AUTHOR = "M. Held and R. M. Karp",
  TITLE = "The traveling-salesman problem and minimum spanning trees",
  JOURNAL = "Operations Research",
  VOLUME = "18",
  YEAR = "1970",
  PAGES = "1138--1162")

@ARTICLE(HK71,
  AUTHOR = "M. Held and R. M. Karp",
  TITLE = "The traveling-salesman problem and minimum spanning trees: part {II}",
  JOURNAL = "Math. Programming",
  VOLUME = "1",
  YEAR = "1971",
  PAGES = "6--25")

@INPROCEEDINGS(HK95,
  AUTHOR = "M. R. Henzinger and V. King",
  TITLE = "Randomized dynamic graph algorithms with polylogarithmic
		  time per operation",
  BOOKTITLE = "Proc. 27th Symp. on Theory of Computing",
  YEAR = "1995",
  PAGES	= "519--527")	  
		  
@INPROCEEDINGS(HK95b,
  AUTHOR = "M. R. Henzinger and V. King",
  TITLE = "Fully dynamic biconnectivity and transitive closure", 
  BOOKTITLE = "Proc. 36th IEEE Symp. Foundations of Computer Science",
  YEAR = "1995",
  PAGES = "664--672",
  ABSTRACT = "This paper presents an algorithm for the fully dynamic
     biconnectivity problem whose running time is exponentially faster
     than all previously known solutions. It is the first dynamic
     algorithm that answers biconnectivity queries in time O(log^2 n) in
     a n-node graph and can be updated after an edge insertion or
     deletion in polylogarithmic time. Our algorithm is a Las-Vegas
     style randomized algorithm with the update time amortized update
     time O(log^4 n). Only recently the best deterministic result for
     this problem was improved to O(sqrt n log^2 n). We also give the
     first fully dynamic and a novel deletions-only transitive closure
     (i.e. directed connectivity) algorithms. These are randomized Monte
     Carlo algorithms. Let n be the number of nodes in the graph and let
     m be the average number of edges in the graph during the whole
     update sequence: The fully dynamic algorithms achieve (1) query
     time O(n / log n) and update time O(m square root n log^2 n + n);
     or (2) query time O(n / logn) and update time O(nm^{mu -1}) log^2 n)
     = O(nm^0.58 log^2 n), where mu is the exponent for boolean matrix
     multiplication (currently mu =2.38). The deletions-only algorithm
     answers queries in time O(n / logn). Its amortized update time is
     O(n log^2 n).")
		  
@INPROCEEDINGS(HL95,
  AUTHOR = "M. R. Henzinger and J. A. {La Poutr\'e}",
  TITLE = "Certificates and fast algorithms for biconnectivity in
		  fully dynamic graphs", 
  BOOKTITLE = "Proc. 3rd European Symp. on Algorithms",
  YEAR = "1995",
  PAGES	= "")	  		  

@ARTICLE(Hb89,
  AUTHOR = "J. Hershberger",
  TITLE = "Finding the visibility graph of a polygon
           in time proportional to its size",
  JOURNAL = algo,
  VOLUME = "4",
  YEAR = "1989",
  PAGES = "141--155")

@INPROCEEDINGS(HRS92,
  AUTHOR = "J. Hershberger and M. Rauch and S. Suri",
  TITLE = "Fully dynamic 2-connectivity on planar graphs",
  BOOKTITLE = "Proc. 3rd Scandinavian Workshop on Algorithm Theory",
  PUBLISHER = "Lecture Notes in Computer Science 621, Springer-Verlag,
              Berlin",
  YEAR = "1992",
  PAGES = "233--244")

@INPROCEEDINGS(HS89,
  AUTHOR = "J. Hershberger and S. Suri",
  TITLE = "Finding tailored partitions",
  BOOKTITLE = "Proc. 5th ACM Symp. Computational Geometry",
  YEAR = "1989",
  PAGES = "255--265")
  
@INPROCEEDINGS(HS91,
  AUTHOR = "J. Hershberger and S. Suri",
  TITLE = "Offline maintenance of planar configurations",
  BOOKTITLE = "Proc. 2rd ACM/SIAM Symp. Discrete Algorithms",
  YEAR = "1991",
  PAGES = "32--41")

@PHDTHESIS(Hol83,
  AUTHOR = "B. Hollenbach",
  TITLE = "Recognition and isomorphism algorithms for circular
	   permutation graphs",
  SCHOOL = "Georgia Institute of Technology, Atlanta",
  YEAR = "1983")

@PHDTHESIS(H87,
  AUTHOR = "R. Hoover",
  TITLE = "Incremental Graph Evaluation",
  SCHOOL = "Department of Computer Science, Cornell University",
  YEAR = "1987",
  NOTE = "Technical Report 87-836")

@ARTICLE(HT73,
  AUTHOR = "J. Hopcroft and R. E. Tarjan",
  TITLE = "Dividing a graph into triconnected components",
  JOURNAL = sicomp,
  VOLUME = "2",
  YEAR = "1973",
  PAGES = "135--158")

@ARTICLE(HT74,
  AUTHOR = "J. Hopcroft and R. E. Tarjan",
  TITLE = "Efficient planarity testing",
  JOURNAL = jacm,
  VOLUME = "21",
  YEAR = "1974",
  PAGES = "549--568")

@ARTICLE(HU73,
  AUTHOR = "J. E. Hopcroft and J. D. Ullman",
  TITLE = "Set merging algorithms",
  JOURNAL = sicomp,  
  VOLUME = "2",
  YEAR = "1973",
  PAGES = "294--303")

@TECHREPORT(H88,
  AUTHOR = "N. Horspool",
  TITLE = "Incremental generation of {LR} parsers",
  INSTITUTION = "Department of Computer Science, University of Victoria",
  YEAR = "1988")

@ARTICLE(IK83,
  AUTHOR = "T. Ibaraki and N. Katoh",
  TITLE = "On-line computation of transitive closure for graphs",
  JOURNAL = ipl,
  VOLUME = "16",
  YEAR = "1983",
  PAGES = "95--97")

@ARTICLE(IA84,
  AUTHOR = "H. Imai and T. Asano",
  TITLE = "Finding the connected components and a maximum clique of an
	   intersection graph of rectangles in the plane",
  JOURNAL = algs,
  VOLUME = "4",
  YEAR = "1984",
  PAGES = "310--323")

@ARTICLE(IW91,
  AUTHOR = "M. Imase and B. M. Waxman",
  TITLE = "Dynamic {Steiner} tree problem",
  JOURNAL = "SIAM J. Discrete Math.",
  VOLUME = "4",
  YEAR = "1991",
  PAGES = "369--384")

%INPROCEEDINGS(Ir90,
%  AUTHOR = "S. Irani",
%  TITLE = "Coloring inductive graphs on-line",
%  BOOKTITLE = "Proc. 31st IEEE Symp. Foundations of Computer Science",
%  YEAR = "1990",
%  PAGES = "470--479",
%  NOTE = "To appear in {\em Algorithmica}")

@ARTICLE(Ir90,
  AUTHOR = "S. Irani",
  TITLE = "Coloring inductive graphs on-line",
  JOURNAL = algo,
  YEAR = "1994",
  VOLUME = 11,
  PAGES = "53-72")

@INPROCEEDINGS(IKP92,
  AUTHOR = "S. Irani and A. Karlin and S. Phillips",
  TITLE = "Strongly competitive algorithms for paging with locality of reference",
  BOOKTITLE = "Proc. 3rd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1992",
  PAGES = "228--236")

@INPROCEEDINGS(IRWS91,
  AUTHOR = "S. Irani and N. Reingold and J. Westbrook and D. D. Sleator",
  TITLE = "Randomized competitive algorithms for the list update problem",
  BOOKTITLE = "Proc. 2nd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1991",
  PAGES = "251--260")

@PHDTHESIS(I91,
  AUTHOR = "G. F. Italiano",
  TITLE = "Dynamic data structures for graphs",
  SCHOOL = "Department of Computer Science, Columbia University",
  MONTH = "April",
  YEAR = "1991")

@ARTICLE(I86,
  AUTHOR = "G. F. Italiano",
  TITLE = "Amortized efficiency of a path retrieval data structure",
  JOURNAL = tcs,
  VOLUME = "48",
  YEAR = "1986",
  PAGES = "273--281")

@ARTICLE(I88,
  AUTHOR = "G. F. Italiano",
  TITLE = "Finding paths and deleting edges in directed acyclic graphs",
  JOURNAL = ipl,
  VOLUME = "28",
  YEAR = "1988",
  PAGES = "5--11")

@INPROCEEDINGS(ILR93,
  AUTHOR = "G. F. Italiano and J. A. {La Poutr\'e} and M. Rauch",
  TITLE = "Fully dynamic planarity testing in planar embedded graphs",
  BOOKTITLE = "Proc. 1st European Symp. Algorithms",
  PUBLISHER = "Lecture Notes in Computer Science 726, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "212--223")

@INPROCEEDINGS(IMN89,
  AUTHOR = "G. F. Italiano and A. {Marchetti Spaccamela} and U. Nanni",
  TITLE = "Dynamic data structures for series parallel digraphs",
  BOOKTITLE = "Proc. Workshop on Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 382, Springer-Verlag, Berlin",
  YEAR = "1989",
  PAGES = "352--372")

@INPROCEEDINGS(IR94,
  AUTHOR = "G. F. Italiano and R. Ramaswami", 
  TITLE = "Mantaining spanning trees of small diameter",
  BOOKTITLE = "Proc. 21st Int. Coll. on Automata, Languages and Programming",
  PUBLISHER = "Lecture Notes in Computer Science, Springer-Verlag, Berlin",
  YEAR = "1994",
  PAGES = "")

@INPROCEEDINGS(IL93,
  AUTHOR = "Z. Ivkovic and E. L. Lloyd",
  TITLE = "Fully dynamic maintenance of vertex cover",
  BOOKTITLE = "Proc. Workshop on Graph-Theoretic Concepts in Computer Science",
  YEAR = "1993",
  PAGES = "?")

@ARTICLE(J90,
  AUTHOR = "H. V. Jagadish",
  TITLE = "A compression technique to materialize transitive closure",
  JOURNAL = "ACM Trans. on Database Systems",
  VOLUME = "15",
  YEAR = "1990",
  PAGES = "558--598")

@ARTICLE(J91,
  AUTHOR = "R. Janardan",
  TITLE = "On maintaining the width and diameter of a planar point-set online",
  JOURNAL = ijcga,
  VOLUME = 3,
  YEAR = 1993,
  PAGES = "331--344",
  NOTE = "See also {\em 2nd Int. Symp. Algorithms}, 1991, pp. 137--149.")

@ARTICLE(JC91,
  AUTHOR = "R. Janardan and S. W. Cheng",
  TITLE = "Efficient distributed algorithms for single-source shortest paths
	   and related problems on plane networks",
  JOURNAL = mst,
  VOLUME = "25",
  YEAR = "1992",
  PAGES = "93--122",
  NOTE = "See also {\em 4th Int. Worksh. Distributed Algorithms},
	  Lecture Notes in Computer Science 486, Springer-Verlag, Berlin,
	  pages 133--150, 1991")

@TECHREPORT(JM91,
  AUTHOR = "D. B. Johnson and P. Metaxas",
  TITLE = "Optimal parallel and sequential algorithms for the vertex
	   updating problem of a minimum spanning tree",
  INSTITUTION = "Dartmouth College, Hanover NH",
  YEAR = "1991",
  NUMBER = "PCS-TR91-159")

@INPROCEEDINGS(JV82,
  AUTHOR = "D. B. Johnson and S. Venkatesan",
  TITLE = "Using divide and conquer to find flows in planar networks in
	   {$O(n^{3/2}\log n)$} time",
  BOOKTITLE = "Proc. 20th Allerton Conf. on Communication,
	       Control, and Computing",
  YEAR = "1982",
  PAGES = "898--905")

@TECHREPORT(JM87,
  AUTHOR = "H. Jung and K. Mehlhorn",
  TITLE = "Parallel algorithms for computing maximum independent set in trees
	   and for updating minimum spanning trees",
  INSTITUTION = "Univ. Saarlandes, Saarbrucken, Germany",
  YEAR = "1987",
  NUMBER = "01")

@INPROCEEDINGS(KP91,
  AUTHOR = "B. Kalyanasundaram and K. Pruhs",
  TITLE = "On-line weighted matching",
  BOOKTITLE = "Proc. 2nd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1991",
  PAGES = "234--240")

@INPROCEEDINGS(KP93,
  AUTHOR = "B. Kalyanasundaram and K. Pruhs",
  TITLE = "Constructing competitive tours from local information",
  BOOKTITLE = "Proc. 20th Int. Colloquium on Automata, Languages and
               Programming",
  PUBLISHER = "Lecture Notes in Computer Science 700, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "102--113")

@ARTICLE(K75,
  AUTHOR = "T. Kameda", 
  TITLE = "On the vector representation of the reachability in planar
          directed graphs", 
  JOURNAL = ipl,
  VOLUME = "3",
  YEAR = "1975", 
  PAGES = "75--77")

@INPROCEEDINGS(DKT91,
  AUTHOR = "A. Kanevsky and R. Tamassia and G. {Di Battista} and J. Chen",
  TITLE = "On-line maintenance of the four-connected components of a graph",
  BOOKTITLE = "Proc. 32nd IEEE Symp. Foundations of Computer Science",
  YEAR = "1991",
  PAGES = "793--801")

@ARTICLE(K87,
  AUTHOR = "M. Kano",
  TITLE = "Maximum and $k$th maximal spanning trees of a weighted graph",
  JOURNAL = "Combinatorica",
  VOLUME = "7",
  YEAR = "1987",
  PAGES = "205--214")

@INPROCEEDINGS(KRT93,
  AUTHOR = "M.-Y. Kao and J. H. Reif and S. R. Tate",
  TITLE = "Searching in an unknown environment:
	   an optimal randomized algorithm for the cow-path problem",
  BOOKTITLE = "Proc. 4th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1993",
  PAGES = "441--447")

@ARTICLE(KT91,
  AUTHOR = "M.-Y. Kao and S. R. Tate",
  TITLE = "Online matching with blocked input",
  JOURNAL = ipl,
  YEAR = "1991",
  VOLUME = "38",
  PAGES = "113--116")

@TECHREPORT(K86,
  AUTHOR = "S. Kaplan",
  TITLE = "Incremental attribute evaluation on graphs",
  INSTITUTION = "University of Illinois at Urbana-Champaign",
  YEAR = "1986",
  NUMBER = "UIUC-DCS-86-18309")

@ARTICLE(KKT95,
  AUTHOR = "D. R. Karger and P. N. Klein and and R. E. Tarjan",
  TITLE = "A randomized linear-time algorithm to find minimum spanning trees",
  JOURNAL = "J. Assoc. Comput. Mach.",
  YEAR = 1995,
  PAGES = "321--328")

@INPROCEEDINGS(KVV90,
  AUTHOR = "R. M. Karp and U. V. Vazirani and V. V. Vazirani",
  TITLE = "An optimal algorithm for on-line bipartite matching",
  BOOKTITLE = "Proc. 22nd ACM Symp. Theory of Computing",
  YEAR = "1990",
  PAGES = "352--358")

@ARTICLE(KT86,
  AUTHOR = "A. V. Karzanov and E. A. Timofeev",
  TITLE = "Efficient algorithm for finding all minimal edge cuts
	   of a nonoriented graph",
  JOURNAL = "Cybernetics",
  YEAR = "1986",
  PAGES = "156--162")

@ARTICLE(KIM81,
  AUTHOR = "N. Katoh and T. Ibaraki and H. Mine",
  TITLE = "An algorithm for finding {$k$} minimum spanning trees",
  JOURNAL = sicomp,
  VOLUME = "10",
  YEAR = "1981",
  PAGES = "247--255")

@INPROCEEDINGS(KI91,
  AUTHOR = "N. Katoh and K. Iwano",
  TITLE = "Efficient algorithms for the minimum range cut problems",
  BOOKTITLE = "Proc. 2nd Worksh. Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 519, Springer-Verlag, Berlin",
  YEAR = "1991",
  PAGES = "80--91")

@INPROCEEDINGS(KTI92,
  AUTHOR = "N. Katoh and T. Tokuyama and K. Iwano",
  TITLE = "On minimum and maximum spanning trees of linearly moving points",
  BOOKTITLE = "Proc. 33rd IEEE Symp. Foundations of Computer Science",
  YEAR = "1992",
  PAGES = "396--405")

@INPROCEEDINGS(K88,
  AUTHOR = "J. M. Keil",
  TITLE = "Approximating the complete {Euclidean} graph",
  BOOKTITLE = "Proc. 1st Scandinavian Workshop on Algorithm Theory",
  PUBLISHER = "Lecture Notes in Computer Science 318, Springer-Verlag, Berlin",
  YEAR = "1988",
  PAGES = "208--213")

@INPROCEEDINGS(KMW96,
  AUTHOR = "S. Khanna and R. Motwani and R. H. Wilson",
  TITLE = "On certificates and lookahead on dynamic graph problems",
  BOOKTITLE = "Proc. 7th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = 1996,
  PAGES = "222--231")

@INPROCEEDINGS(KMV91,
  AUTHOR = "S. Khuller and S. G. Mitchell and V. V. Vazirani",
  TITLE = "On-line algorithms for weighted bipartite matching
	   and stable marriages",
  BOOKTITLE = "Proc. 18th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science 510, Springer-Verlag,
              Berlin",
  YEAR = "1991",
  PAGES = "728--738")

@ARTICLE(Ki81,
  AUTHOR = "H. A. Kierstead",
  TITLE = "An effective version of {Dilworth's} theorem",
  JOURNAL = "Trans. Amer. Math. Soc.",
  VOLUME = "268",
  YEAR = "1981",
  PAGES = "63--77")

@ARTICLE(Ki88,
  AUTHOR = "H. A. Kierstead",
  TITLE = "The linearity of first-fit coloring of interval graphs",
  JOURNAL = "SIAM J. Discrete Math.",
  VOLUME = "1",
  YEAR = "1988",
  PAGES = "526--530")

@ARTICLE(KPT94,
  AUTHOR = "H. A. Kierstead and S. G. Penrice and W. T. Trotter",
  TITLE = "On-line coloring and recursive graph theory",
  JOURNAL = "SIAM J. Discrete Math.",
  VOLUME = 7,
  YEAR = 1994,
  PAGES = "72--89")

@ARTICLE(KT81,
  AUTHOR = "H. A. Kierstead and W. T. Trotter",
  TITLE = "An extremal problem in recursive combinatorics",
  JOURNAL = "Congressus Numerantium",
  VOLUME = "33",
  YEAR = "1981",
  PAGES = "143--153")

@INCOLLECTION(KT93,
  AUTHOR = "H. A. Kierstead and W. T. Trotter",
  TITLE = "Planar graph coloring with an uncooperative partner",
  BOOKTITLE = "Planar Graphs",
  PUBLISHER = "Amer. Math. Soc. series in Discrete Mathematics
	       and Theoretical Computer Science, vol. 9",
  EDITOR = "W. T. Trotter",
  YEAR = "1993",
  PAGES = "85--93")

@INPROCEEDINGS(K95,
  AUTHOR = "V. King",
  TITLE = "A simpler minimum spanning tree verification algorithm",
  BOOKTITLE = "Proc. 4th Worksh. Algorithms and Data Structures",
  YEAR = 1995,
  PAGES = "440--448")

@INPROCEEDINGS(KRT91,
  AUTHOR = "V. King and S. Rao and R. E. Tarjan",
  TITLE = "A faster deterministic maximum flow algorithm",
  BOOKTITLE = "Proc. 3rd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1992",
  PAGES = "157--164")

@ARTICLE(K83,
  AUTHOR = "D. Kirkpatrick",
  TITLE = "Optimal search in planar subdivision",
  JOURNAL = sicomp,
  VOLUME = "12",
  YEAR = "1983",
  PAGES = "28--35")

@ARTICLE(KR88,
  AUTHOR = "P. N. Klein and J. H. Reif",
  TITLE = "An efficient parallel algorithm for planarity",
  JOURNAL = jcss,
  VOLUME = "37",
  YEAR = "1988",
  PAGES = "465--477")

@INPROCEEDINGS(KS92,
  AUTHOR = "P. N. Klein and S. Sairam",
  TITLE = "A parallel randomized approximation scheme for shortest paths",
  BOOKTITLE = "Proc. 24th ACM Symp. Theory of Computing",
  YEAR = "1992",
  PAGES = "750--758")

@INPROCEEDINGS(KS93,
  AUTHOR = "P. N. Klein and S. Sairam",
  TITLE = "Fully dynamic approximation schemes for shortest path problems
	   in planar graphs",
  BOOKTITLE = "Proc. 3rd Worksh. Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 709, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "442--451")

@BOOK(K68, 
  AUTHOR = "D. E. Knuth", 
  TITLE = "The Art of Computer Programming Vol. 1: Fundamental Algorithms",
  PUBLISHER = "Addison-Wesley, Reading, Mass.", 
  YEAR = "1968")

@ARTICLE(KMK91,
  AUTHOR = "N. Kobayashi and S. Masuda and T. Kashiwabara",
  TITLE = "Algorithms to obtain a maximal planar Hamilton subgraph",
  JOURNAL = "IEICE Transactions",
  YEAR = 1991,
  VOLUME = "E74",
  PAGES = "657--664")

@ARTICLE(K53,
  AUTHOR = "A. N. Kolmogorov", 
  TITLE = "On the notion of algorithm",
  JOURNAL = "Uspehi Mat. Nauk.",
  VOLUME = "8",
  PAGES = "175--176", 
  YEAR = "1953")

@ARTICLE(K30,
  AUTHOR = "C. Kuratowski",
  TITLE = "Sur les probl\`{e}mes des courbes gauches en {Topologie}",
  JOURNAL = "Fund. Math.",
  VOLUME = "15",
  YEAR = "1930",
  PAGES = "271--283")

@INPROCEEDINGS(L90b,
  AUTHOR = "J. A. {La Poutr\'e}",
  TITLE = "Lower bounds for the union-find and the split-find problem
          on pointer machines",
  BOOKTITLE = "Proc. 22nd ACM Symp. Theory of Computing",
  YEAR = "1990",
  PAGES = "34--44")

@PHDTHESIS(L91,
  AUTHOR = "J. A. {La Poutr\'e}",
  TITLE = "Dynamic graph algorithms and data structures",
  SCHOOL = "Department of Computer Science, Utrecht University",
  MONTH = "September",
  YEAR = "1991")

@TECHREPORT(L91b,
  AUTHOR = "J. A. {La Poutr\'e}",
  TITLE = "Maintenance of 2- and 3-connected components of graphs,
          part {II}: 2- and 3-edge-connected components and
          2-vertex-connected components", 
  INSTITUTION = "Department of Computer Science, Utrecht University",
  YEAR = "1991",
  NUMBER = "ALCOM-91-145")

@MISC(L92,
  AUTHOR = "J. A. {La Poutr\'e}",
  TITLE = "Personal communication",
  YEAR = "1992")

@INPROCEEDINGS(L92i,
  AUTHOR = "J. A. {La Poutr\'e}",
  TITLE = "Maintainance of triconnected components of graphs",
  BOOKTITLE = "Proc. 19th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science 623, Springer-Verlag, Berlin",
  YEAR = "1992",
  PAGES = "354--365")

@INPROCEEDINGS(L94,
  AUTHOR = "J. A. {La Poutr\'e}",
  TITLE = "Alpha-algorithms for incremental planarity testing",
  BOOKTITLE = "Proc. 26th ACM Symp. Theory of Computing",
  YEAR = "1994")

@INPROCEEDINGS(LvL88,
  AUTHOR = "J. A. {La Poutr\'e} and J. van Leeuwen",
  TITLE = "Maintenance of transitive closure and transitive reduction of
          graphs",
  BOOKTITLE = "Proc. Workshop on Graph-Theoretic Concepts in Computer Science",
  PUBLISHER = "Lecture Notes in Computer Science 314, Springer-Verlag, Berlin",
  YEAR = "1988",
  PAGES = "106--120")

@ARTICLE(LVO93,
  AUTHOR = "J. A. {La Poutr\'e} and J. van Leeuwen and M. H. Overmars",
  TITLE = "Maintenance of 2- and 3-connected components of Graphs, Part {I}: 
          2- and 3-edge-connected components",
  JOURNAL = "Discrete Mathematics",
  VOLUME = "114",
  YEAR = "1993", 
  PAGES = "329--359")

@INPROCEEDINGS(LW94,
  AUTHOR = "J. A. {La Poutr\'e} and J. Westbrook",
  TITLE = "Dynamic two-connectivity with backtracking",
  BOOKTITLE = "Proc. 5th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1994",
  PAGES = "204-212")

@BOOK(L76,
  AUTHOR = "E. L. Lawler",
  TITLE = "Combinatorial Optimization: Networks and Matroids",
  PUBLISHER = "Holt, Reinhart and Winston, New York",
  YEAR = "1976")

@BOOK(LLRS85,
  AUTHOR = "E. L. Lawler and J. K. Lenstra and A. H. G. {Rinnooy Kan}
	    and D. B. Shmoys",
  TITLE = "The Traveling Salesman Problem",
  PUBLISHER = "John Wiley \& Sons, Chichester",
  YEAR = "1985")

@INPROCEEDINGS(LEC67,
  AUTHOR = "A. Lempel and S. Even and I. Cederbaum",
  TITLE = "An algorithm for planarity testing of graphs",
  BOOKTITLE = "Theory of Graphs: International Symposium",
  YEAR = "1967",
  PAGES = "215--232")

@ARTICLE(LC89,
  AUTHOR = "C. C. Lin and R. C. Chang",
  TITLE = "On the dynamic shortest path problem",
  JOURNAL = "J. Information Processing",
  YEAR = "1990",
  VOLUME = "13",
  PAGES = "470--476",
  NOTE = "See also {\em Int. Worksh. Discrete Algorithms and Complexity},
	  pages 203--212, 1989")

@INPROCEEDINGS(Li90,
  AUTHOR = "A. Lingas",
  TITLE = "Efficient parallel algorithms for path problems in planar
	   directed graphs",
  BOOKTITLE = "Proc. International Symp. Algorithms",
  PUBLISHER = "Lecture Notes in Computer Science 450, Springer-Verlag, Berlin",
  YEAR = "1990",
  PAGES = "447--457")

@ARTICLE(LLLMP79,
  AUTHOR = "W. Lipski and E. Lodi and F. Luccio and C. Mugnai and L. Pagli",
  TITLE = "On two dimensional data organization {II}",
  JOURNAL = "Fund. Inform.",
  VOLUME = "2",
  YEAR = "1979",
  PAGES = "245--260")

@INPROCEEDINGS(LT77,
  AUTHOR = "R. J. Lipton and R. E. Tarjan",
  TITLE = "Applications of a planar separator theorem",
  BOOKTITLE = "Proc. 18th IEEE Symp. Foundations of Computer Science",

  YEAR = "1977",
  PAGES = "162--170")

@UNPUBLISHED(LYY93,
  AUTHOR = "J. Lobo and Q. Yang and C. Yu",
  TITLE = "Computing the transitive closure in disjunctive databases",
  NOTE = "Manuscript",
  YEAR = "1993")

@ARTICLE(LST89,
  AUTHOR = "L. Lov\'{a}sz and M. Saks and W. T. Trotter",
  TITLE = "An on-line graph coloring algorithm with sublinear performance
	   ratio",
  JOURNAL = "Discrete Math.",
  VOLUME = "75",
  YEAR = "1989",
  PAGES = "319--325")

@INPROCEEDINGS(LNO94,
  AUTHOR = "M. G. Luby and J. Naor and A. Orda",
  TITLE = "Tight bounds for dynamic storage allocation",
  BOOKTITLE = "Proc. 5th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = 1994,
  PAGES = "724--732")

@INPROCEEDINGS(Lu78,
  AUTHOR = "G. S. Lueker",
  TITLE = "A data structure for orthogonal range queries",
  BOOKTITLE = "Proc. 19th IEEE Symp. Foundations of Computer Science",
  YEAR = "1978",
  PAGES = "28-34")

@ARTICLE(LW82,
  AUTHOR = "G. S. Lueker and D. E. Willard",
  TITLE = "A Data Structure for Dynamic Range Queries",
  JOURNAL = ipl,
  VOLUME =15,
  YEAR = 1982,
  PAGES = "209--213")

@ARTICLE(MMS90,
  AUTHOR = "M. S. Manasse and L. A. McGeoch and D. D. Sleator",
  TITLE = "Competitive algorithms for server problems",
  JOURNAL = algs,
  VOLUME = "11",
  YEAR = "1990",
  PAGES = "208--230")

@ARTICLE(MR72,
  AUTHOR = "A. B. Manaster and J. G. Rosenstein",
  TITLE = "Effective matchmaking (recursion theoretic aspects of a theorem
	   of {Philip} {Hall})",
  JOURNAL = "Proc. Lond. Math. Soc.",
  VOLUME = "25",
  YEAR = "1972",
  PAGES = "615--654")

@ARTICLE(MR73,
  AUTHOR = "A. B. Manaster and J. G. Rosenstein",
  TITLE = "Effective matchmaking and $k$-chromatic graphs",
  JOURNAL = "Proc. Amer. Math. Soc.",
  VOLUME = "39",
  YEAR = "1973",
  PAGES = "371--378")

@INPROCEEDINGS(MNR93,
  AUTHOR = "A. Marchetti-Spaccamela and U. Nanni and H. Rohnert",
  TITLE = "On-line Graph Algorithms for Incremental Compilation",
  BOOKTITLE = "Proc. Workshop on Graph-Theoretic Concepts in Computer Science",
  YEAR = "1993",
  PAGES = "?")

@ARTICLE(MS89,
  AUTHOR = "O. Marcotte and S. Suri",
  TITLE = "Fast matching algorithms for points on a polygon",
  JOURNAL = sicomp,
  VOLUME = "20",
  YEAR = "1991",
  PAGES = "405--422",
  NOTE = "See also {\em 5th ACM Symp. Computational Geometry},
	  pages 302--314, 1989")

@ARTICLE(MPTW84,
  AUTHOR = "S. Martello and W. R. Pulleyblank and P. Toth and D. de Werra",
  TITLE = "Balanced optimization problems",
  JOURNAL = "Operations Research Lett.",
  VOLUME = 3,
  YEAR = 1984,
  PAGES = "275--278")

@INCOLLECTION(MMI72,
  AUTHOR = "D. W. Matula and G. Marble and J. D. Isaacson",
  TITLE = "Graph coloring algorithms",
  BOOKTITLE = "Graph Theory and Computing",
  EDITOR = "R. C. Read",
  PUBLISHER = "Academic Press, New York",
  YEAR = "1972",
  PAGES = "109--122")

@ARTICLE(MP90,
  AUTHOR = "E. W. Mayr and C. G. Plaxton",
  TITLE = "On the spanning trees of weighted graphs",
  JOURNAL = "Combinatorica",
  VOLUME = "12",
  PAGES = "433--447",
  YEAR = "1992",
  NOTE = "See also {\em Worksh. WG '88 Graph-Theoretical Concepts in Computer
	  Science}, pp. 394--405, Lecture Notes in Computer Science 344,
	  Springer-Verlag, Berlin, 1989")

@INCOLLECTION(M79,
  AUTHOR = "C. J. H. McDiarmid",
  TITLE = "Colouring random graphs badly",
  BOOKTITLE = "Graph Theory and Combinatorics",
  EDITOR = "R. J. Wilson",
  PUBLISHER = "Pitman Research Notes in Mathematics 34",
  YEAR = "1979",
  PAGES = "76--86")

@ARTICLE(MS91,
  AUTHOR = "L. A. McGeoch and D. D. Sleator",
  TITLE = "A strongly competitive randomized paging algorithm",
  JOURNAL = algo,
  VOLUME = "6",
  YEAR = "1991",
  PAGES = "816--825")

@INPROCEEDINGS(McS94,
  AUTHOR = "R. M. McConnell and J. P. Spinrad",
  TITLE = "Linear-time modular decomposition and efficient transitive
	   orientation of comparability graphs",
  BOOKTITLE = "Proc. 5th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1994",
  PAGES = "536--545")

@ARTICLE(MHG88,
  AUTHOR = "N. Megiddo and S. L. Hakimi and M. R. Garey and D. S. Johnson
	    and C. H. Papadimitriou",
  TITLE = "The complexity of searching a graph",
  JOURNAL = jacm,
  VOLUME = "35",
  YEAR = "1988",
  PAGES = "18--44")

@BOOK(M84,
  AUTHOR = "K. Mehlhorn",
  TITLE = "Data Structures and Algorithms 3: Multi-Dimensional Searching and
	   Computational Geometry",
  PUBLISHER = "Springer-Verlag",
  YEAR = "1984")

@ARTICLE(MNA88,
  AUTHOR = "K. Mehlhorn and S. {N\"aher} and H. Alt",
  TITLE = "A lower bound for the complexity of the union-split-find problem",
  JOURNAL = sicomp,
  VOLUME = "17", 
  YEAR = "1988",
  PAGES = "1093--1102")

@ARTICLE(MN90,
  AUTHOR = "K. Mehlhorn and S. {N\"aher}", 
  TITLE = "Dynamic Fractional Cascading",
  JOURNAL = algo, 
  VOLUME = "5", 
  YEAR = "1990",
  PAGES = "215--241")

@ARTICLE(MOM90,
  AUTHOR = "K. Mehlhorn and S. Meiser and C. {O'Dunlaing}",
  TITLE = "On the construction of abstract {Voronoi} diagrams",
  JOURNAL = dcg,
  VOLUME = 6,
  YEAR = 1991,
  PAGES = "211--224",
  NOTE = "See also {\em Symp. Theor. Aspects of Comp. Sci.}, 1990, pp. 227--239")

@ARTICLE(M86,
  AUTHOR = "G. L. Miller",
  TITLE = "Finding small simple cycle separators for 2-connected planar
	   graphs",
  JOURNAL = jcss,
  VOLUME = "32",
  YEAR = "1986",
  PAGES = "265--279")

@INPROCEEDINGS(MN89,
  AUTHOR = "G. L. Miller and J. Naor",
  TITLE = "Flow in planar graphs with multiple sources and sinks",
  BOOKTITLE = "Proc. 30th IEEE Symp. Foundations of Computer Science",
  YEAR = "1989",
  PAGES = "112--117")

@INPROCEEDINGS(MTV91,
  AUTHOR = "G. L. Miller and S.-H. Teng and S. A. Vavasis",
  TITLE = "A unified geometric approach to graph separators",
  BOOKTITLE = "32nd IEEE Symp. Foundations of Computer Science",
  YEAR = "1991",
  PAGES = "538--547")

@INPROCEEDINGS(MT90,
  AUTHOR = "G. L. Miller and W. P. Thurston",
  TITLE = "Separators in two and three dimensions",
  BOOKTITLE = "Proc. 22nd ACM Symp. Theory of Computing",
  YEAR = "1990",
  PAGES = "300--309")

@INPROCEEDINGS(MV91,
  AUTHOR = "G. L. Miller and S. A. Vavasis",
  TITLE = "Density graphs and separators",
  BOOKTITLE = "2nd ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1991",
  PAGES = "331--336")

@ARTICLE(MPSY88,
  AUTHOR = "C. Monma and M. Paterson and S. Suri and F. Yao",
  TITLE = "Computing {Euclidean} maximum spanning trees",
  JOURNAL = algo,
  VOLUME = "5",
  YEAR = "1990",
  PAGES = "407--419",
  NOTE = "See also {\em 4th Symp. Comp. Geom.}, 1988, pp. 239--249.")

@ARTICLE(MuS89,
  AUTHOR = "J. H. Muller and J. Spinrad",
  TITLE = "Incremental modular decomposition",
  JOURNAL = jacm,
  VOLUME = 36,
  YEAR = 1989,
  PAGES = "1--19")

@ARTICLE(Mu88,
  AUTHOR = "K. Mulmuley",
  TITLE = "A fast planar partition algorithm, {I}",
  JOURNAL = "J. Symbolic Computation",
  VOLUME = "10",
  YEAR = "1990",
  PAGES = "253--280",
  NOTE = "See also {\em 29th Symp. Found. Comp. Sci.}, 1988, pp. 580--589")

@INPROCEEDINGS(Mu91a,
  AUTHOR = "K. Mulmuley",
  TITLE = "Randomized multidimensional search trees: dynamic sampling",
  BOOKTITLE = "Proc. 7th ACM Symp. Computational Geometry",
  YEAR = "1991",
  PAGES = "121--131")

@INPROCEEDINGS(Mu91b,
  AUTHOR = "K. Mulmuley",
  TITLE = "Randomized multidimensional search trees:
	   lazy balancing and dynamic shuffling",
  BOOKTITLE = "Proc. 32nd IEEE Symp. Foundations of Computer Science",

  YEAR = "1991",
  PAGES = "180--196")

@BOOK(Mu93,
  AUTHOR = "K. Mulmuley",
  TITLE = "Computational Geometry,
	   an Introduction through Randomized Algorithms",
  PUBLISHER = "Prentice Hall",
  YEAR = "1993")

@ARTICLE(NI90,
  AUTHOR = "H. Nagamochi and T. Ibaraki",
  TITLE = "Linear time algorithms for finding a sparse $k$-connected spanning
          subgraph of a $k$-connected graph",
  JOURNAL = algo,
  VOLUME = "7",
  YEAR = "1992",
  PAGES = "583--596")

@ARTICLE(Nf86,
  AUTHOR = "S. Nfatos",
  TITLE = "On gallery watchman in grids",
  JOURNAL = ipl,
  VOLUME = "23",
  YEAR = "1986",
  PAGES = "99--102")

@INPROCEEDINGS(RSY95,
  AUTHOR = "S. Nikoletseas and J. Reif and P. Spirakis and M. Yung",
  TITLE = "Stochastic graphs have short memory: fully dynamic
		  connectivity in poly-log expected time",
  BOOKTITLE = "Proc. 22nd Int. Coll. on Automata, Languages and Programming",
  PUBLISHER = "Lecture Notes in Computer Science, Springer-Verlag, Berlin",
  YEAR = "1995")

@BOOK(NC88,
  AUTHOR = "T. Nishizeki and N. Chiba",
  TITLE = "Planar Graphs: Theory and Algorithms",
  PUBLISHER = "Annals of Discrete Mathematics 32, North Holland",
  YEAR = "1988")

@ARTICLE(OSTT83,
  AUTHOR = "T. Ohtsuki and M. Sato and M. Tachibana and and S. Torii",
  TITLE = "Minimum partitioning of rectilinear regions",
  JOURNAL = "Trans. Inform. Proc. Soc. of Japan",
  YEAR = 1983)

@BOOK(Ork87,
  AUTHOR = "J. {O'Rourke}",
  TITLE = "Art Gallery Theorems and Algorithms",
  PUBLISHER = "Oxford University Press",
  YEAR = "1987")

@BOOK(O83,
  AUTHOR = "M. Overmars",
  TITLE = "The design of dynamic data structures",
  PUBLISHER = "Lecture Notes in Computer Science 156, Springer-Verlag",
  YEAR = 1983)

@ARTICLE(OvL81,
  AUTHOR = "M. H. Overmars and J. {van Leeuwen}",
  TITLE = "Maintenance of configurations in the plane",
  JOURNAL = jcss,
  VOLUME = "23",
  YEAR = "1981",
  PAGES = "224--233")

@INPROCEEDINGS(OW88,
  AUTHOR = "M. H. Overmars and E. Welzl",
  TITLE = "New methods for computing visibility graphs",
  BOOKTITLE = "Proc. 4th ACM Symp. Computational Geometry",
  YEAR = "1988",
  PAGES = "164--171")

@ARTICLE(PSZ92,
  AUTHOR = "G. E. Pantziou and P. G. Spirakis and C. D. Zaroliagis",
  TITLE = "Efficient parallel algorithms for shortest paths in planar
	   digraphs",
  JOURNAL = "BIT",
  VOLUME = "32",
  YEAR = "1992",
  PAGES = "215--236")

@ARTICLE(PY89,
  AUTHOR = "C. Papadimitriou and M. Yannakakis",
  TITLE = "Shortest paths without a map",
  JOURNAL = tcs,
  VOLUME = "84",
  YEAR = "1991",
  PAGES = "127--150",
  NOTE = "See also {\em 16th Int. Colloq. Automata, Languages and Programming},
	  Lecture Notes in Computer Science 372, Springer-Verlag, Berlin,
	  pages 610--620, 1989")

@INPROCEEDINGS(PS80, 
  AUTHOR = "J. Paul and W. Simon",
  TITLE = "Decision trees and random access machines", 
  BOOKTITLE = "Smposium uber Logik und Algorithmik",
  YEAR = "1980",
  NOTE = "See also K. Mehlhorn, Sorting and Searching, pp. 85--97,
  Springer-Verlag, Berlin, 1984")

@ARTICLE(PK93,
  AUTHOR = "S. Pawagi and O. Kaser",
  TITLE = "Optimal parallel algorithms for multiple updates of minimum
	   spanning trees",
  JOURNAL = algo,
  VOLUME = "9",
  YEAR = "1993",
  PAGES = "357--381")

@ARTICLE(PR86,
  AUTHOR = "S. Pawagi and I. V. Ramakrishnan",
  TITLE = "An {$O(\log n)$} algorithm for parallel update of minimum
	   spanning trees",
  JOURNAL = ipl,
  VOLUME = "22",
  YEAR = "1986",
  PAGES = "223--229")

@INPROCEEDINGS(PW93,
  AUTHOR = "S. Phillips and J. Westbrook",
  TITLE = "Online load balancing and network flow",
  BOOKTITLE = "Proc. 25th ACM Symp. Theory of Computing",
  YEAR = "1993",
  PAGES = "402--411")

@BOOK(PS85,
  AUTHOR = "F. P. Preparata and M. I. Shamos",
  TITLE = "Computational Geometry---An Introduction",
  PUBLISHER = "Springer-Verlag, New York",
  YEAR = "1985")

@ARTICLE(PT89,
  AUTHOR = "F. P. Preparata and R. Tamassia",
  TITLE = "Fully dynamic point location in a monotone subdivision",
  JOURNAL = sicomp,
  VOLUME = "18",
  YEAR = "1989",
  PAGES = "811--830")

@ARTICLE(Pu90,
  AUTHOR = "W. Pugh",
  TITLE = "Skip lists: a probabilistic alternative to balanced trees",
  JOURNAL = cacm,
  VOLUME = "33",
  YEAR = "1990",
  PAGES = "668--676")

@INPROCEEDINGS(RS89,
  AUTHOR = "P. Raghavan and M. Snir",
  TITLE = "Memory versis randomization in on-line algorithms",
  BOOKTITLE = "Proc. 16th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science 372, Springer-Verlag, Berlin",
  YEAR = "1989",
  PAGES = "687--703")

@INPROCEEDINGS(RR89,
  AUTHOR = "V. Ramachandran and J. H. Reif",
  TITLE = "An optimal parallel algorithm for graph planarity",
  BOOKTITLE = "30th IEEE Symp. Foundations of Computer Science",
  YEAR = "1989",
  PAGES = "282--287")

@PHDTHESIS(RR91,
  AUTHOR = "G. Ramalingam",
  TITLE = "Bounded incremental compilation",  
  SCHOOL = "Department of Computer Science, University of Wisconsin at Madison",
  MONTH = "August",
  YEAR = "1993")

@ARTICLE(Ram93, 
  AUTHOR = "R. Ramaswami",
  TITLE = "Multi-wavelength lightwave networks for computer communication",
  JOURNAL = "IEEE Communications Magazine", 
  VOLUME = "31",
  YEAR = "1993", 
  PAGES = "78--88")

@INPROCEEDINGS(Ra93,
  AUTHOR = "H. Ramesh",
  TITLE = "On traversing layered graphs on-line",
  BOOKTITLE = "Proc. 4th ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1993",
  PAGES = "412--421")

@INPROCEEDINGS(R92,
  AUTHOR = "M. Rauch",
  TITLE = "Fully dynamic biconnectivity in graphs",
  BOOKTITLE = "Proc. 33rd IEEE Symp. Foundations of Computer Science",
  YEAR = "1992",
  PAGES = "50--59")

@INPROCEEDINGS(R93,
  AUTHOR = "M. Rauch",
  TITLE = "Improved data structures for fully dynamic biconnectivity",
  BOOKTITLE = "Proc. 26th Symp. Theory of Computing",
  YEAR = "1994",
  PAGES = "")

@PHDTHESIS(R,
  AUTHOR = "M. Rauch",
  TITLE = "Fully Dynamic Graph Algorithms and Their Data Structures",
  SCHOOL = "Department of Computer Science, Princeton University",
  MONTH = "December",
  YEAR = "1992",
  NOTE = "Technical Report CS-TR-402-92")

@ARTICLE(Re87,
  AUTHOR = "J. H. Reif",
  TITLE = "A topological approach to dynamic graph connectivity",
  JOURNAL = ipl,
  VOLUME = "25",
  YEAR = "1987",
  PAGES = "65--70")

@BOOK(R84,
  AUTHOR = "T. Reps",
  TITLE = "Generating language-based environments",
  PUBLISHER = "The M.I.T. Press, Cambridge, MA",
  YEAR = "1984")

@INPROCEEDINGS(R85,
  AUTHOR = "H. Rohnert",
  TITLE = "A dynamization of the all pairs least cost path problem",
  BOOKTITLE = "Proc. 2nd Symp. Theoretical Aspects of Computer
              Science",
  PUBLISHER = "Lecture Notes in Computer Science 182, Springer-Verlag,
              Berlin",
  YEAR = "1985",
  PAGES = "279--286")

@INPROCEEDINGS(RA92,
  AUTHOR = "T. Roos and G. Albers",
  TITLE = "Maintaining proximity in higher dimensional spaces",
  BOOKTITLE = "Proc. Mathematical Foundations of Computer Science",
  PUBLISHER = "Lecture Notes in Computer Science 629, Springer-Verlag, Berlin",
  YEAR = "1992",
  PAGES = "483--493")

@INPROCEEDINGS(RSS93,
  AUTHOR = "G. Rote and C. Schwarz and J. Snoeyink",
  TITLE = "Maintaining the approximate width of a set of points in the plane",
  BOOKTITLE = "Proc. 5th Canad. Conf. Computational Geometry",
  YEAR = 1993,
  PAGES = "258--263")

@INPROCEEDINGS(S93,
  AUTHOR = "S. Sairam",
  TITLE = "A fully dynamic data structure for reachability in planar digraphs",
  BOOKTITLE = "Proc. 1st European Symp. Algorithms",
  PUBLISHER = "Lecture Notes in Computer Science 726, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "?")

@INPROCEEDINGS(Sa91,
  AUTHOR = "J. S. Salowe",
  TITLE = "Construction of multidimensional spanner graphs,
	   with application to minimum spanning trees",
  BOOKTITLE = "Proc. 7th ACM Symp. Computational Geometry",
  YEAR = "1991",
  PAGES = "256--271")

@INPROCEEDINGS(Sa92,
  AUTHOR = "J. S. Salowe",
  TITLE = "On {Euclidean} spanner graphs with small degree",
  BOOKTITLE = "Proc. 8th ACM Symp. Computational Geometry",
  YEAR = "1992",
  PAGES = "186--191")

@ARTICLE(ST86,
  AUTHOR = "N. Sarnak and R. E. Tarjan",
  TITLE = "Planar point location using persistent search trees",
  JOURNAL = cacm,
  VOLUME = "29",
  YEAR = "1986",
  PAGES = "669--679")

@TECHREPORT(SV90,
  AUTHOR = "A. Sch{\"a}ffer and P. Varman",
  TITLE = "Parallel batch update of minimum spanning trees",
  INSTITUTION = "Rice University, Houston TX",
  YEAR = "1990",
  NUMBER = "COMP-TR90-140")

@ARTICLE(Sc80,
  AUTHOR = "J. H. Schmerl",
  TITLE = "Recursive colorings of graphs",
  JOURNAL = "Canad. J. Math.",
  VOLUME = "32",
  YEAR = "1980",
  PAGES = "821--830")

@ARTICLE(S,
  AUTHOR = "A. Sch{\"o}nhage",
  TITLE = "Storage modification machines",
  JOURNAL = sicomp,
  VOLUME = "9",
  YEAR = "1980",
  PAGES = "490--508")

@INPROCEEDINGS(SSS92,
  AUTHOR = "C. Schwarz and M. Smid and J. Snoeyink",
  TITLE = "An optimal algorithm for the on-line closest pair problem",
  BOOKTITLE = "Proc. 8th ACM Symp. Computational Geometry",
  YEAR = "1992",
  PAGES = "330--336")

@INPROCEEDINGS(SC91,
  AUTHOR = "O. Schwarzkopf",
  TITLE = "Dynamic maintenance of geometric structures made easy",
  BOOKTITLE = "Proc. 32nd IEEE Symp. Foundations of Computer Science",
  YEAR = "1991",
  PAGES = "197--206")

@ARTICLE(SV86,
  AUTHOR = "R. Sedgewick and J. Vitter",
  TITLE = "Shortest paths in {Euclidean} graphs",
  JOURNAL = algo,
  VOLUME = "1",
  YEAR = "1986",
  PAGES = "31--48")

@ARTICLE(Se90,
  AUTHOR = "R. Seidel",
  TITLE = "Small-dimensional linear programming and convex hulls made easy",
  JOURNAL = dcg,
  VOLUME = "6",
  YEAR = "1991",
  PAGES = "423--434",
  NOTE = "See also {\em 6th Symp. Comp. Geom.}, 1990, pp. 211--215")

@INPROCEEDINGS(SH75,
  AUTHOR = "M. I. Shamos and D. Hoey",
  TITLE = "Closest-point problems",
  BOOKTITLE = "Proc. 16th IEEE Symp. Foundations of Computer Science",
  YEAR = "1975",
  PAGES = "151--162")

@ARTICLE(SHI90,
  AUTHOR = "T. Shimatani and T. Hirata and Y. Inagaki",
  TITLE = "An on-line algorithm for computing the transitive closure of
	   a graph",
  JOURNAL = "Trans. of the Institute of Electronics, Information and
	     Communication Engineers",
  YEAR = "1990",
  VOLUME = "J73D-I",
  PAGES = "705--706",
  NOTE = "In Japanese")

@TECHREPORT(SS85,
  AUTHOR = "J. B. Sidney and G. Steiner",
  TITLE = "Optimal sequencing by modular decomposition",
  INSTITUTION = "Univ. Ottawa",
  YEAR = 1985,
  NUMBER = "85-9")

@ARTICLE(ST83,
  AUTHOR = "D. D. Sleator and R. E. Tarjan",
  TITLE = "A data structure for dynamic trees",
  JOURNAL = jcss,
  VOLUME = "24",
  YEAR = "1983",
  PAGES = "362--381")

@ARTICLE(ST85,
  AUTHOR = "D. D. Sleator and R. E. Tarjan",
  TITLE = "Self-adjusting binary search trees",
  JOURNAL = jacm,
  VOLUME = "32",
  YEAR = "1985",
  PAGES = "652--686")

@ARTICLE(ST85-lu,
  AUTHOR = "D. D. Sleator and R. E. Tarjan",
  TITLE = "Amortized efficiency of list update and paging rules",
  JOURNAL = cacm,
  VOLUME = "28",
  YEAR = "1985",
  PAGES = "202--208")

@INPROCEEDINGS(Sl89,
  AUTHOR = "M. \'{S}lusarek",
  TITLE = "A coloring algorithm for interval graphs",
  BOOKTITLE = "Proc. Mathematical Foundations of Computer Science",
  PUBLISHER = "Lecture Notes in Computer Science 379, Springer-Verlag, Berlin",
  YEAR = "1989",
  PAGES = "471--480")

@ARTICLE(Sm91,
  AUTHOR = "M. Smid",
  TITLE = "Maintaining the minimal distance of a point set
	   in polylogarithmic time",
  JOURNAL = dcg,
  VOLUME = "7",
  YEAR = "1992",
  PAGES = "415--431",
  NOTE = "See also {\em 2nd Symp. Discrete Algorithms}, pages 1--6, 1991")

@PHDTHESIS(Spi82,
  AUTHOR = "J. Spinrad",
  TITLE = "Two dimensional partial orders",
  SCHOOL = "Princeton University",
  YEAR = 1982)

@ARTICLE(Spi85,
  AUTHOR = "J. Spinrad",
  TITLE = "On comparability and permutation graphs",
  JOURNAL = sicomp,
  VOLUME = 14,
  YEAR = 1985,
  PAGES = "658--670")

@ARTICLE(SP75,
  AUTHOR = "P. M. Spira and A. Pan",
  TITLE = "On finding and updating spanning trees and shortest paths",
  JOURNAL = sicomp,
  VOLUME = "4",
  YEAR = "1975",
  PAGES = "375--380")

@PHDTHESIS(Ste82,
  AUTHOR = "G. Steiner",
  TITLE = "Machine scheduling with precedence constraints",
  SCHOOL = "Dept. of Combinatorics and Optimization, Univ. Waterloo, Canada",
  YEAR = 1982)

@INPROCEEDINGS(Su90,
  AUTHOR = "K. J. Supowit",
  TITLE = "New techniques for some dynamic closest-point and
	   farthest-point problems",
  BOOKTITLE = "Proc. 1st ACM-SIAM Symp. Discrete Algorithms",
  YEAR = "1990",
  PAGES = "84--90")

@INPROCEEDINGS(SG94,
  AUTHOR = "B. Swaminathan and K. Goldberg",
  TITLE = "An incremental distributed algorithm for computing
	   biconnected components",
  BOOKTITLE = "8th Int. Worksh. Distributed Algorithms",
  YEAR = 1994,
  NOTE = "To appear")

@INPROCEEDINGS(T88,
  AUTHOR = "R. Tamassia",
  TITLE = "A dynamic data structure for planar graph embedding",
  BOOKTITLE = "Proc. 15th Int. Colloquium on Automata, Languages
              and Programming",
  PUBLISHER = "Lecture Notes in Computer Science 317, Springer-Verlag,
              Berlin",
  YEAR = "1988",
  PAGES = "576--590")

@ARTICLE(TP90,
  AUTHOR = "R. Tamassia and F. P. Preparata",
  TITLE = "Dynamic maintenance of planar digraphs, with applications",
  JOURNAL = "Algorithmica",
  VOLUME = "5",
  YEAR = "1990",
  PAGES = "509--527")

@ARTICLE(TT93,
  AUTHOR = "R. Tamassia and I. G. Tollis",
  TITLE = "Dynamic reachability in planar digraphs with one source and
          one sink", 
  JOURNAL = tcs, 
  VOLUME = "119", 
  YEAR = "1993", 
  PAGES = "331--344")

@ARTICLE(T72,
  AUTHOR = "R. E. Tarjan",
  TITLE = "Depth-first search and linear graph algorithms",
  JOURNAL = sicomp,
  VOLUME = "1",
  YEAR = "1972",
  PAGES = "146--160")

@ARTICLE(T75,
  AUTHOR = "R. E. Tarjan",
  TITLE = "Efficiency of a good but not linear set union algorithms",
  JOURNAL = jacm,
  VOLUME = "22",
  YEAR = "1975",
  PAGES = "215--225")

@ARTICLE(T79,
  AUTHOR = "R. E. Tarjan",
  TITLE = "A class of algorithms which require nonlinear time to maintain
          disjoint sets",
  JOURNAL = jcss,
  VOLUME = "18",
  YEAR = "1979",
  PAGES = "110--127")

@BOOK(T83,
  AUTHOR = "R. E. Tarjan",
  TITLE = "Data Structures and Network Algorithms",
  PUBLISHER = "CBMS-NSF Regional Conference Series in Applied Mathematics,
              SIAM",
  VOLUME = "44",
  YEAR = "1983")

@ARTICLE(T85,
  AUTHOR = "R. E. Tarjan",
  TITLE = "Amortized computational complexity",
  JOURNAL = "SIAM J. Alg. Disc. Meth.",
  VOLUME = "6",
  YEAR = "1985",
  PAGES = "306--318")

@ARTICLE(TvL84,
  AUTHOR = "R. E. Tarjan and J. {van} Leeuwen",
  TITLE = "Worst-case analysis of set union algorithms",
  JOURNAL = jacm,
  VOLUME= "31",
  YEAR = "1984",
  PAGES = "245--281")

@PHDTHESIS(T91,
  AUTHOR = "S.-H. Teng",
  TITLE = "Points, spheres, and separators: a unified geometric approach
	   to graph partitioning",
  SCHOOL = "Carnegie Mellon University",
  YEAR = "1991")

@PHDTHESIS(T89,
  AUTHOR = "R. Thurimella",
  TITLE = "Techniques for the design of parallel graph algorithms",
  SCHOOL = "University of Texas, Austin",
  YEAR = "1989")

@BOOK(Thu88,
  AUTHOR = "W. P. Thurston",
  TITLE = "The geometry and topology of 3-manifolds",
  PUBLISHER = "Princeton University Notes",
  YEAR = "1988")

@BOOK(T92, 
  AUTHOR = "W. T. Trotter", 
  TITLE = "Combinatorics and Partially Ordered Sets: Dimension Theory",
  PUBLISHER = "The John Hopkins University Press, Baltimore and London",
  YEAR = "1992")

@ARTICLE(Ts88,
  AUTHOR = "Y. H. Tsin",
  TITLE = "On handling vertex deletion in updating minimum spanning trees",
  JOURNAL = ipl,
  VOLUME = "27",
  YEAR = "1988",
  PAGES = "167--168")

@BOOK(T66, 
  AUTHOR = "W. T. Tutte",
  TITLE = "Connectivity in graphs", 
  PUBLISHER = "University of Toronto Press", 
  YEAR = "1966")

@BOOK(T84,
  AUTHOR = "W. T. Tutte",
  TITLE = "Graph Theory",
  PUBLISHER = "Cambridge University Press",
  YEAR = "1984")

@ARTICLE(V88,
  AUTHOR = "P. M. Vaidya",
  TITLE = "Minimum spanning trees in {$k$}-dimensional space",
  JOURNAL = sicomp,
  VOLUME = "17",
  YEAR = "1988",
  PAGES = "572--582")

@ARTICLE(V89,
  AUTHOR = "P. M. Vaidya",
  TITLE = "Geometry helps in matching",
  JOURNAL = sicomp,
  VOLUME = "18",
  YEAR = "1989",
  PAGES = "1201--1225")

@ARTICLE(V89-lp,
  AUTHOR = "P. M. Vaidya",
  TITLE = "Speeding up linear programming using fast matrix multiplication",
  BOOKTITLE = "30th IEEE Symp. Foundations of Computer Science",
  YEAR = "1989",
  PAGES = "332--337")

@ARTICLE(V91,
  AUTHOR = "P. M. Vaidya",
  TITLE = "A sparse graph almost as good as the complete graph
	   on points in {$K$} dimensions",
  JOURNAL = dcg,
  VOLUME = "6",
  YEAR = "1991",
  PAGES = "369--381")

@ARTICLE(V77,
  AUTHOR = "P. {van} Emde Boas",
  TITLE = "Preserving order in a forest in less than logarithmic time
           and linear space",
  JOURNAL = ipl,
  VOLUME = "6",
  YEAR = "1977",
  PAGES = "80--82")

@ARTICLE(VKZ77, 
  AUTHOR = "P. {van} Emde Boas and R. Kaas and E. Zijlstra", 
  TITLE = "Design and implementation of an efficient priority queue",
  JOURNAL = mst, 
  VOLUME = "10", 
  YEAR = "1977",
  PAGES = "99--127")

@ARTICLE(VD88,
  AUTHOR = "P. Varman and K. Deshi",
  TITLE = "A parallel vertex insertion algorithm for minimum spanning trees",
  JOURNAL = tcs,
  VOLUME = "58",
  YEAR = "1988",
  PAGES = "379--397")

@INPROCEEDINGS(Ve91,
  AUTHOR = "G. Vegter",
  TITLE = "Dynamically maintaining the visibility graph",
  BOOKTITLE = "Proc. 2nd Workshop on Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 519, Springer-Verlag, Berlin",
  YEAR = "1991",
  PAGES = "425--436")

@ARTICLE(Vi92,
  AUTHOR = "S. Vishwanathan",
  TITLE = "Randomized online graph coloring",
  JOURNAL = algs,
  YEAR = "1992",
  VOLUME = "13",
  PAGES = "657--669")

@ARTICLE(WP67,
  AUTHOR = "D. J. A. Welsh and M. J. D. Powell",
  TITLE = "An upper bound for the chromatic number of a graph
	   and its applications to timetabling problems",
  JOURNAL = "Computer J.",
  VOLUME = "10",
  YEAR = "1967",
  PAGES = "85--87")

@PHDTHESIS(W89,
  AUTHOR = "J. Westbrook",
  TITLE = "Algorithms and data structures for dynamic graph problems",
  SCHOOL = "Department of Computer Science, Princeton University",
  MONTH = "October",
  YEAR = "1989",
  NOTE = "Technical Report CS-TR-229-89")

@INPROCEEDINGS(W92,
  AUTHOR = "J. Westbrook",
  TITLE = "Fast incremental planarity testing",
  BOOKTITLE = "Proc. 19th Int. Colloquium on Automata, Languages and
              Programming",
  PUBLISHER = "Lecture Notes in Computer Science, Springer-Verlag 623,
              Berlin",
  YEAR = "1992",
  PAGES = "342--353")

@ARTICLE(WT89,
  AUTHOR = "J. Westbrook and R. E. Tarjan",
  TITLE = "Amortized analysis of algorithms for set union with backtracking",
  JOURNAL = sicomp,
  VOLUME = "18",
  YEAR = "1989",
  PAGES = "1--11")

@ARTICLE(WT92,
  AUTHOR = "J. Westbrook and R. E. Tarjan",
  TITLE = "Maintaining bridge-connected and biconnected components on-line",
  JOURNAL = algo,
  VOLUME = "7",
  YEAR = "1992",
  PAGES = "433-464")

@INPROCEEDINGS(WY93,
  AUTHOR = "J. Westbrook and D. C. K. Yan",
  TITLE = "Greedy algorithms for the on-line {Steiner} tree and generalized
	   {Steiner} problems",
  BOOKTITLE = "Proc. 3rd Worksh. Algorithms and Data Structures",
  PUBLISHER = "Lecture Notes in Computer Science 709, Springer-Verlag, Berlin",
  YEAR = "1993",
  PAGES = "622--633")

@ARTICLE(W30,
  AUTHOR = "H. Whitney",
  TITLE = "Non-separable and planar graphs",
  JOURNAL = "Trans. Amer. Math. Soc.",
  VOLUME = "34",
  YEAR = "1930",
  PAGES = "339--362")

@ARTICLE(WL85,
  AUTHOR = "D. E. Willard and G. S. Lueker",
  TITLE = "Adding Range Restriction Capability to Dynamic Data Structures",
  JOURNAL = jacm,
  VOLUME = 32,
  YEAR = 1985,
  PAGES = "597--617")

@INCOLLECTION(W70,
  AUTHOR = "M. R. Williams",
  TITLE = "The colouring of very large graphs",
  BOOKTITLE = "Combinatorial Structures and their Applications",
  PUBLISHER = "Gordon and Breach, New York",
  YEAR = "1970",
  PAGES = "477--478")

@INPROCEEDINGS(Y90,
  AUTHOR = "M. Yannakakis",
  TITLE = "Graph theoretic methods in database theory",
  BOOKTITLE = "Proc. ACM Conf. on Principles of Database Systems",
  YEAR = "1990",
  PAGES = "230-242")

@ARTICLE(Y81,
  AUTHOR = "A. C. Yao",
  TITLE = "Should tables be sorted?",
  JOURNAL = jacm,
  VOLUME = "31",
  YEAR = "1984",
  PAGES = "245--281")

@ARTICLE(Y82,
  AUTHOR = "A. C. Yao",
  TITLE = "On constructing minimum spanning trees in {$k$}-dimensional space
	   and related problems",
  JOURNAL = sicomp,
  VOLUME = "11",
  YEAR = "1982",
  PAGES = "721--736")

%TECHREPORT(Y88,
%  AUTHOR = "D. M. Yellin",
%  TITLE = "A dynamic transitive closure algorithm",
%  INSTITUTION = "IBM Research Division, T. J. Watson Research Center",
%  YEAR = "1988",
%  NUMBER = "13535",
%  NOTE = "To appear in {\em Acta Informatica}")

@ARTICLE(Y88,
  AUTHOR = "D. M. Yellin",
  TITLE = "Speeding up dynamic transitive closure for bounded degree graphs",
  JOURNAL = acta,
  VOLUME = "30",
  YEAR = "1993",
  PAGES = "369--384")

@ARTICLE(YS88,
  AUTHOR = "D. M. Yellin and R. Strom",
  TITLE = "{INC}: a language for incremental computations",
  JOURNAL = "ACM Trans. Prog. Languages and Systems",
  VOLUME = "13",
  YEAR = "1991",
  PAGES = "211--236",
  NOTE = "See also {\em ACM SIGPLAN Conf. Programming Language Design and
          Implementation}, pages 115--124, 1988")