Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification -- a technique for speeding up dynamic graph algorithms (extended abstract). In 33rd Annual Symposium on Foundations of Computer Science, pages 60-69, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

General Terms: Algorithms

Additional Key Words and Phrases: Dynamic graph algorithms, minimum spanning trees, edge and vertex connectivity

Selected references

• Giuseppe Amato, Giuseppe Cattaneo, and Giuseppe F. Italiano. Experimental analysis of dynamic minimum spanning tree algorithms (extended abstract). In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 314-323, New Orleans, Louisiana, 5-7 January 1997.

• Giuseppe Di Battista and Roberto Tamassia. On-line graph algorithms with SPQR-trees. In Michael S. Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, volume 443 of Lecture Notes in Computer Science, pages 598-611, Warwick University, England, 16-20 July 1990. Springer-Verlag.

• A. Michael Berman, Marvin C. Paull, and Barbara G. Ryder. Proving relative lower bounds for incremental algorithms. Acta Informatica, 27(7):665-683, 1989.

• Joseph Cheriyan, Ming-Yang Kao, and Ramakrishna Thurimella. Scan-first search and sparse certificates: An improved parallel algorithms for k-vertex connectivity. SIAM Journal on Computing, 22(1):157-174, February 1993.

• Joseph Cheriyan and Ramakrishna Thurimella. Algorithms for parallel k-vertex connectivity and sparse certificates (extended abstract). In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 391-401, New Orleans, Louisiana, 6-8 May 1991.

• Paul F. Dietz and Daniel D. Sleator. Two algorithms for maintaining order in a list. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 365-372, New York City, 25-27 May 1987.

• Brandon Dixon, Monika Rauch, and Robert E. Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing, 21(6):1184-1192, December 1992.

• David Eppstein. Offline algorithms for dynamic minimum spanning tree problems. Journal of Algorithms, 17(2):237-250, September 1994.

• David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification I. Planarity testing and minimum spanning trees. Journal of Computer and System Sciences, 52(1):3-27, February 1996.

• David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery Westbrook, and Moti Yung. Maintenance of a minimum spanning forest in a dynamic plane graph. Journal of Algorithms, 13(1):33-54, March 1992.

• Tomás Feder and Milena Mihail. Balanced matroids. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 26-38, Victoria, British Columbia, Canada, 4-6 May 1992.

• D. Fernàndez-Baca, G. Slutzki and D. Eppstein. Using Sparsification for Parametric Minimum Spanning Tree Problems Nordic Journal of Computing, 3(4):352-366, Winter 1996.

• Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing, 14(4):781-798, November 1985.

• Greg N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spaning trees. SIAM Journal on Computing, 26(2):484-538, April 1997.

• Greg N. Frederickson and Mandayam A. Srinivas. Algorithms and data structures for an expanded family of matroid intersection problems. SIAM Journal on Computing, 18(1):112-138, February 1989.

• Harold N. Gabow. Applications of a poset representation to edge connectivity and graph rigidity. In 32nd Annual Symposium on Foundations of Computer Science, pages 812-821, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 112-122, New Orleans, Louisiana, 6-8 May 1991.

• Harold N. Gabow and Matthias Stallmann. Efficient algorithms for graphic intersection and parity (extended abstract). In Wilfried Brauer, editor, Automata, Languages and Programming, 12th Colloquium, volume 194 of Lecture Notes in Computer Science, pages 210-220, Nafplion, Greece, 15-19 July 1985. Springer-Verlag.

• Zvi Galil and Giuseppe F. Italiano. Maintaining biconnected components of dynamic planar graphs. In Javier Leach Albert and Burkhard Monien and Mario Rodríguez-Artalejo, editors, Automata, Languages and Programming, 18th International Colloquium, volume 510 of Lecture Notes in Computer Science, pages 339-350, Madrid, Spain, 8-12 July 1991. Springer-Verlag.

• Zvi Galil and Giuseppe F. Italiano. Fully dynamic algorithms for 2-edge connectivity. SIAM Journal on Computing, 21(6):1047-1069, December 1992.

• Zvi Galil and Giuseppe F. Italiano. Maintaining the 3-edge-connected components of a graph on-line. SIAM Journal on Computing, 22(1):11-28, February 1993.

• Xiaofeng Han, Pierre Kelsen, Vijaya Ramachandran, and Robert Tarjan. Computing minimal spanning subgraphs in linear time. SIAM Journal on Computing, 24(6):1332-1358, December 1995.

• Monika Rauch Henzinger. Fully dynamic biconnectivity in graphs. Algorithmica, 13(6):503-538, June 1995.

• Monika Rauch Henzinger and Valerie King. Fully dynamic biconnectivity and transitive closure. In 36th Annual Symposium on Foundations of Computer Science, pages 664-672, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.

• Monika Rauch Henzinger and Valerie King. Randomized dynamic graph algorithms with polylogarithmic time per operation. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 519-527, Las Vegas, Nevada, 29 May-1 June 1995.

• Monika Rauch Henzinger and Valerie King. Maintaining minimum spanning trees in dynamic graphs. In Pierpaolo Degano and Robert Gorrieri and Alberto Marchetti-Spaccamela, editors, Automata, Languages and Programming, 24th International Colloquium, volume 1256 of Lecture Notes in Computer Science, pages 594-604, Bologna, Italy, 7-11 July 1997. Springer-Verlag.

• Monika Rauch Henzinger and Johannes A. La Poutré Certificates and fast algorithms for biconnectivity in fully-dynamic graphs. In Paul G. Spirakis, editor, Algorithms -- ESA '95, Third Annual European Symposium, volume 979 of Lecture Notes in Computer Science, pages 171-184, Corfu, Greece, 25-27 September 1995. Springer.

• J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM Journal on Computing, 2(3):135-158, September 1973.

• Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, and Jianer Chen. On-line maintenance of the four-connected components of a graph (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, pages 793-801, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2):321-328, March 1995.

• Sanjeev Khanna, Rajeev Motwani, and Randall H. Wilson. On certificates and lookahead in dynamic graph problems. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 222-231, Atlanta, Georgia, 28-30 January 1996.

• Valerie King. A simpler minimum spanning tree verification algorithm. In Selim G. Akl and Frank K. H. A. Dehne and Jörg-Rüdiger Sack and Nicola Santoro, editors, Algorithms and Data Structures, 4th International Workshop, volume 955 of Lecture Notes in Computer Science, pages 440-448, Kingston, Ontario, Canada, 16-18 August 1995. Springer.

• Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583-596, 1992.

• Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, June 1983.

• Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, June 1972.

• Jeffery Westbrook and Robert Endre Tarjan. Maintaining bridge-connected and biconnected components on-line. Algorithmica, 7:433-464, 1992.

Shortcuts: