% Bibliography of key references for "LaTeX for Thesis and Large Documents"
% For use with BibTeX

@preamble{"\providecommand{\noopsort}[1]{}"}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: My papers
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@InProceedings{Sandlund20b,
	author =	{Bryce Sandlund and Sebastian Wild},
	title =	{Lazy Search Trees},
	Booktitle = {Proceedings of the 61st Annual Symposium on Foundations of Computer Science},
	year =	{2020}
}

@inproceedings{ElZein18,
	Author = {Hicham El-Zein and Meng He and J. Ian Munro and Bryce Sandlund},
	Booktitle = {26th Annual European Symposium on Algorithms},
	Pages = {25:1--25:13},
	Title = {{Improved Time and Space Bounds for Dynamic Range Mode}},
	Volume = {112},
	Year = {2018}}

@inproceedings{Peng19,
	Author = {Richard Peng and Bryce Sandlund and Daniel D. Sleator},
	Booktitle = {Algorithms and Data Structures Symposium},
	Title = {Optimal Offline Dynamic 2,3-Edge/Vertex Connectivity},
	Year = {2019}}

@inproceedings{Munro20,
	Author = {J. Ian Munro and Bryce Sandlund and Corwin Sinnamon},
	Booktitle = {17th Scandinavian Symposium and Workshop on Algorithm Theory},
	Title = {Space-Efficient Data Structures for Lattices},
	Year = {2020}}

@inproceedings{Lovett20,
	Author = {Nalin Bhardwaj and Antonio Molina Lovett and Bryce Sandlund},
	Booktitle = {17th Scandinavian Symposium and Workshop on Algorithm Theory},
	Title = {A Simple Algorithm for Minimum Cuts in Near-Linear Time},
	Year = {2020}}

@InProceedings{ElZein19,
	author =	{Hicham El{-}Zein and Meng He and J. Ian Munro and Yakov Nekrich and Bryce Sandlund},
	title =	{On Approximate Range Mode and Range Selection},
	booktitle =	{30th International Symposium on Algorithms and Computation},
	year =	{2019}
}

@InProceedings{Sandlund20a,
	author =	{Bryce Sandlund and Yinzhan Xu},
	title =	{Faster Dynamic Range Mode},
	booktitle =	{47th International Colloquium on Automata, Languages and Programming},
	year =	{2020}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: Lattices
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@inproceedings{FM06,
	title={Succinct representation of finite abelian groups},
	author={Farzan, Arash and Munro, J Ian},
	booktitle={Proceedings of the 2006 international symposium on Symbolic and algebraic computation},
	pages={87--92},
	year={2006},
	organization={ACM}
}

@article{BM99,
	Author = {Brodnik, Andrej and Munro, J Ian},
	Journal = {SIAM Journal on Computing},
	Number = {5},
	Pages = {1627--1640},
	Publisher = {SIAM},
	Title = {Membership in constant time and almost-minimum space},
	Volume = {28},
	Year = {1999}}

@article{Hab96,
	Author = {Habib, Michel and Nourine, Lhouari},
	Journal = {Theoretical Computer Science},
	Number = {2},
	Pages = {391--405},
	Publisher = {Elsevier},
	Title = {Tree structure for distributive lattices and its applications},
	Volume = {165},
	Year = {1996}}

@article{Hab01,
	Author = {Habib, Michel and Medina, Raoul and Nourine, Lhouari and Steiner, George},
	Journal = {Discrete Applied Mathematics},
	Number = {2},
	Pages = {169--187},
	Publisher = {Elsevier},
	Title = {Efficient algorithms on distributive lattices},
	Volume = {110},
	Year = {2001}}

@book{Dav02,
	Author = {Davey, Brian A and Priestley, Hilary A},
	Publisher = {Cambridge university press},
	Title = {Introduction to lattices and order},
	Year = {2002}}

@article{Day70,
	Author = {Day, Alan},
	Journal = {Canad. Math. Bull},
	Pages = {253--254},
	Title = {A simple solution to the word problem for lattices},
	Volume = {13},
	Year = {1970}}

@article{DSST89,
	Author = {Driscoll, James R and Sarnak, Neil and Sleator, Daniel D and Tarjan, Robert E},
	Journal = {Journal of computer and system sciences},
	Number = {1},
	Pages = {86--124},
	Publisher = {Elsevier},
	Title = {Making data structures persistent},
	Volume = {38},
	Year = {1989}}

@article{EHR02,
	Author = {Ern{\'e}, Marcel and Heitzig, Jobst and Reinhold, J{\"u}rgen},
	Journal = {Electron. J. Combin},
	Number = {1},
	Pages = {23},
	Title = {On the number of distributive lattices},
	Volume = {9},
	Year = {2002}}

@article{Bir37,
	title={Rings of sets},
	author={Birkhoff, Garrett},
	journal={Duke Mathematical Journal},
	volume={3},
	number={3},
	pages={443--454},
	year={1937},
	publisher={Duke University Press}
}

@article{Cas99,
	Author = {Caseau, Yves and Habib, Michel and Nourine, Lhouari and Raynaud, Olivier},
	Journal = {Computational Intelligence},
	Number = {1},
	Pages = {50--62},
	Publisher = {Wiley Online Library},
	Title = {Encoding of multiple inheritance hierarchies and partial orders},
	Volume = {15},
	Year = {1999}}

@article{KW80,
	Author = {Kleitman, DJ and Winston, KJ},
	Journal = {Annals of Discrete Mathematics},
	Pages = {243--249},
	Publisher = {Elsevier},
	Title = {The asymptotic number of lattices},
	Volume = {6},
	Year = {1980}}

@inproceedings{Jac89,
	Author = {Guy Jacobson},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/focs/Jacobson89},
	Booktitle = {30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989},
	Crossref = {DBLP:conf/focs/FOCS30},
	Doi = {10.1109/SFCS.1989.63533},
	Pages = {549--554},
	Timestamp = {Fri, 19 May 2017 01:26:00 +0200},
	Title = {Space-efficient Static Trees and Graphs},
	Url = {https://doi.org/10.1109/SFCS.1989.63533},
	Year = {1989},
	Bdsk-Url-1 = {https://doi.org/10.1109/SFCS.1989.63533}}

@proceedings{DBLP:conf/focs/FOCS30,
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/focs/FOCS30},
	Isbn = {0-8186-1982-1},
	Publisher = {{IEEE} Computer Society},
	Timestamp = {Mon, 15 Dec 2014 18:48:45 +0100},
	Title = {30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989},
	Url = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=260},
	Year = {1989},
	Bdsk-Url-1 = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=260}}

@incollection{Mun04,
	Author = {J. Ian Munro and S. Srinivasa Rao},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/reference/crc/Munro004},
	Booktitle = {Handbook of Data Structures and Applications.},
	Crossref = {DBLP:reference/crc/2004dsa},
	Doi = {10.1201/9781420035179.ch37},
	Timestamp = {Wed, 14 Jun 2017 20:39:06 +0200},
	Title = {Succinct Representation of Data Structures},
	Url = {https://doi.org/10.1201/9781420035179.ch37},
	Year = {2004},
	Bdsk-Url-1 = {https://doi.org/10.1201/9781420035179.ch37}}

@book{DBLP:reference/crc/2004dsa,
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/reference/crc/2004dsa},
	Doi = {10.1201/9781420035179},
	Editor = {Dinesh P. Mehta and Sartaj Sahni},
	Isbn = {978-1-58488-435-4},
	Publisher = {Chapman and Hall/CRC},
	Timestamp = {Tue, 16 May 2017 14:02:19 +0200},
	Title = {Handbook of Data Structures and Applications},
	Url = {https://doi.org/10.1201/9781420035179},
	Year = {2004},
	Bdsk-Url-1 = {https://doi.org/10.1201/9781420035179}}

@book{Nav16,
	Author = {Gonzalo Navarro},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/books/daglib/0038982},
	Isbn = {978-1-10-715238-0},
	Publisher = {Cambridge University Press},
	Timestamp = {Tue, 14 Mar 2017 15:14:29 +0100},
	Title = {Compact Data Structures - {A} Practical Approach},
	Year = {2016}}

@article{DBLP:journals/algorithmica/FarzanM14,
	Author = {Arash Farzan and J. Ian Munro},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/journals/algorithmica/FarzanM14},
	Doi = {10.1007/s00453-012-9664-0},
	Journal = {Algorithmica},
	Number = {1},
	Pages = {16--40},
	Timestamp = {Wed, 17 May 2017 14:25:14 +0200},
	Title = {A Uniform Paradigm to Succinctly Encode Various Families of Trees},
	Url = {https://doi.org/10.1007/s00453-012-9664-0},
	Volume = {68},
	Year = {2014},
	Bdsk-Url-1 = {https://doi.org/10.1007/s00453-012-9664-0}}

@inproceedings{DBLP:conf/icalp/FarzanRR09,
	Author = {Arash Farzan and Rajeev Raman and S. Srinivasa Rao},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/icalp/FarzanRR09},
	Booktitle = {Automata, Languages and Programming, 36th International Colloquium, {ICALP} 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part {I}},
	Crossref = {DBLP:conf/icalp/2009-1},
	Doi = {10.1007/978-3-642-02927-1_38},
	Pages = {451--462},
	Timestamp = {Thu, 15 Jun 2017 21:39:15 +0200},
	Title = {Universal Succinct Representations of Trees?},
	Url = {https://doi.org/10.1007/978-3-642-02927-1_38},
	Year = {2009},
	Bdsk-Url-1 = {https://doi.org/10.1007/978-3-642-02927-1_38}}

@proceedings{DBLP:conf/icalp/2009-1,
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/icalp/2009-1},
	Doi = {10.1007/978-3-642-02927-1},
	Editor = {Susanne Albers and Alberto Marchetti{-}Spaccamela and Yossi Matias and Sotiris E. Nikoletseas and Wolfgang Thomas},
	Isbn = {978-3-642-02926-4},
	Publisher = {Springer},
	Series = {Lecture Notes in Computer Science},
	Timestamp = {Tue, 23 May 2017 01:08:21 +0200},
	Title = {Automata, Languages and Programming, 36th International Colloquium, {ICALP} 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part {I}},
	Url = {https://doi.org/10.1007/978-3-642-02927-1},
	Volume = {5555},
	Year = {2009},
	Bdsk-Url-1 = {https://doi.org/10.1007/978-3-642-02927-1}}

@article{DBLP:journals/algorithmica/GolynskiOR014,
	Author = {Alexander Golynski and Alessio Orlandi and Rajeev Raman and S. Srinivasa Rao},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/journals/algorithmica/GolynskiOR014},
	Doi = {10.1007/s00453-013-9767-2},
	Journal = {Algorithmica},
	Number = {4},
	Pages = {906--924},
	Timestamp = {Thu, 15 Jun 2017 21:22:26 +0200},
	Title = {Optimal Indexes for Sparse Bit Vectors},
	Url = {https://doi.org/10.1007/s00453-013-9767-2},
	Volume = {69},
	Year = {2014},
	Bdsk-Url-1 = {https://doi.org/10.1007/s00453-013-9767-2}}

@article{DBLP:journals/algorithmica/MunroN16,
	Author = {J. Ian Munro and Patrick K. Nicholson},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/journals/algorithmica/MunroN16},
	Doi = {10.1007/s00453-015-0047-1},
	Journal = {Algorithmica},
	Number = {2},
	Pages = {445--473},
	Timestamp = {Wed, 17 May 2017 14:25:15 +0200},
	Title = {Succinct Posets},
	Url = {https://doi.org/10.1007/s00453-015-0047-1},
	Volume = {76},
	Year = {2016},
	Bdsk-Url-1 = {https://doi.org/10.1007/s00453-015-0047-1}}

@inproceedings{Far06,
	Author = {Arash Farzan and J. Ian Munro},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/issac/FarzanM06},
	Booktitle = {Symbolic and Algebraic Computation, International Symposium, {ISSAC} 2006, Genoa, Italy, July 9-12, 2006, Proceedings},
	Crossref = {DBLP:conf/issac/2006},
	Doi = {10.1145/1145768.1145788},
	Pages = {87--92},
	Timestamp = {Fri, 15 Dec 2006 08:18:21 +0100},
	Title = {Succinct representation of finite abelian groups},
	Url = {http://doi.acm.org/10.1145/1145768.1145788},
	Year = {2006},
	Bdsk-Url-1 = {http://doi.acm.org/10.1145/1145768.1145788},
	Bdsk-Url-2 = {https://doi.org/10.1145/1145768.1145788}}

@proceedings{DBLP:conf/issac/2006,
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/issac/2006},
	Editor = {Barry M. Trager},
	Isbn = {1-59593-276-3},
	Publisher = {{ACM}},
	Timestamp = {Fri, 15 Dec 2006 08:18:21 +0100},
	Title = {Symbolic and Algebraic Computation, International Symposium, {ISSAC} 2006, Genoa, Italy, July 9-12, 2006, Proceedings},
	Year = {2006}}

@inproceedings{Mun16,
	Author = {J. Ian Munro},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/issac/Munro16},
	Booktitle = {Proceedings of the {ACM} on International Symposium on Symbolic and Algebraic Computation, {ISSAC} 2016, Waterloo, ON, Canada, July 19-22, 2016},
	Crossref = {DBLP:conf/issac/2016},
	Doi = {10.1145/2930889.2930944},
	Pages = {5--8},
	Timestamp = {Tue, 19 Jul 2016 11:33:18 +0200},
	Title = {Succinct Data Structures ... Potential for Symbolic Computation?},
	Url = {http://doi.acm.org/10.1145/2930889.2930944},
	Year = {2016},
	Bdsk-Url-1 = {http://doi.acm.org/10.1145/2930889.2930944},
	Bdsk-Url-2 = {https://doi.org/10.1145/2930889.2930944}}

@proceedings{DBLP:conf/issac/2016,
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/conf/issac/2016},
	Editor = {Sergei A. Abramov and Eugene V. Zima and Xiao{-}Shan Gao},
	Isbn = {978-1-4503-4380-0},
	Publisher = {{ACM}},
	Timestamp = {Tue, 19 Jul 2016 11:21:49 +0200},
	Title = {Proceedings of the {ACM} on International Symposium on Symbolic and Algebraic Computation, {ISSAC} 2016, Waterloo, ON, Canada, July 19-22, 2016},
	Url = {http://dl.acm.org/citation.cfm?id=2930889},
	Year = {2016},
	Bdsk-Url-1 = {http://dl.acm.org/citation.cfm?id=2930889}}

@inproceedings{Ben97,
	Author = {Bentley, Jon L and Sedgewick, Robert},
	Booktitle = {Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms},
	Organization = {Society for Industrial and Applied Mathematics},
	Pages = {360--369},
	Title = {Fast algorithms for sorting and searching strings},
	Year = {1997}}

@article{HK73,
	Author = {Hopcroft, John E and Karp, Richard M},
	Journal = {SIAM Journal on computing},
	Number = {4},
	Pages = {225--231},
	Publisher = {SIAM},
	Title = {An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs},
	Volume = {2},
	Year = {1973}}

@article{Dil50,
	Author = {Dilworth, Robert P},
	Journal = {Annals of Mathematics},
	Pages = {161--166},
	Publisher = {JSTOR},
	Title = {A decomposition theorem for partially ordered sets},
	Year = {1950}}

@article{TV99,
	Author = {Talamo, Maurizio and Vocca, Paola},
	Journal = {SIAM journal on computing},
	Number = {5},
	Pages = {1783--1805},
	Publisher = {SIAM},
	Title = {An efficient data structure for lattice operations},
	Volume = {28},
	Year = {1999}}

@article{TV97,
	Author = {Talamo, Maurizio and Vocca, Paola},
	Journal = {Theoretical Computer Science},
	Number = {2},
	Pages = {373--392},
	Publisher = {Elsevier},
	Title = {A data structure for lattice representation},
	Volume = {175},
	Year = {1997}}

@incollection{TV94,
	title={Fast lattice browsing on sparse representation},
	author={Talamo, Maurizio and Vocca, Paola},
	booktitle={Orders, Algorithms, and Applications},
	pages={186--204},
	year={1994},
	publisher={Springer}
}

@article{KL71,
	Author = {Klotz, Walter and Lucht, Lutz},
	Journal = {Journal f{\"u}r die Reine und Angewandte Mathematik},
	Pages = {58--68},
	Title = {Endliche Verb{\"a}nde.},
	Volume = {247},
	Year = {1971}}

@phdthesis{Win79,
	Author = {Winston, Kenneth James},
	School = {Massachusetts Institute of Technology},
	Title = {Asymptotic analysis of lattices and tournament score vectors.},
	Year = {1979}}

@article{K62,
	title={Topological sorting of large networks},
	author={Kahn, Arthur B},
	journal={Communications of the ACM},
	volume={5},
	number={11},
	pages={558--562},
	year={1962},
	publisher={ACM}
}

@article{ABLN89,
	title={Efficient implementation of lattice operations},
	author={A{\"\i}t-Kaci, Hassan and Boyer, Robert and Lincoln, Patrick and Nasr, Roger},
	journal={ACM Transactions on Programming Languages and Systems (TOPLAS)},
	volume={11},
	number={1},
	pages={115--146},
	year={1989},
	publisher={ACM}
}

@incollection{Wil82,
	title={Restructuring lattice theory: an approach based on hierarchies of concepts},
	author={Wille, Rudolf},
	booktitle={Ordered sets},
	pages={445--470},
	year={1982},
	publisher={Springer}
}

@inproceedings{MS18,
	title={Time and space efficient representations of distributive lattices},
	author={Munro, J Ian and Sinnamon, Corwin},
	booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms},
	pages={550--567},
	year={2018},
	organization={Society for Industrial and Applied Mathematics}
}

@book{Gan05,
	title={Formal concept analysis: foundations and applications},
	author={Ganter, Bernhard and Stumme, Gerd and Wille, Rudolf},
	volume={3626},
	year={2005},
	publisher={Springer}
}

@book{Davey02,
	title={Introduction to Lattices and Order},
	author={Davey, Brian A. and Priestley, Hilary A.},
	year={1990},
	publisher={Cambridge University Press}
}

@article{DD06,
	title={Exploiting the lattice of ideals representation of a poset},
	author={De Loof, Karel and De Meyer, Hans and De Baets, Bernard},
	journal={Fundamenta Informaticae},
	volume={71},
	number={2, 3},
	pages={309--321},
	year={2006},
	publisher={IOS Press}
}

@article{NR99,
	title={A fast algorithm for building lattices},
	author={Nourine, Lhouari and Raynaud, Olivier},
	journal={Information processing letters},
	volume={71},
	number={5-6},
	pages={199--204},
	year={1999},
	publisher={Elsevier}
}

@article{Tho04,
	title={Compact oracles for reachability and approximate distances in planar digraphs},
	author={Thorup, Mikkel},
	journal={Journal of the ACM (JACM)},
	volume={51},
	number={6},
	pages={993--1024},
	year={2004},
	publisher={ACM}
}

@article{Pat11,
	title={Unifying the landscape of cell-probe lower bounds},
	author={P{\u{a}}tra{\c{s}}cu, Mihai},
	journal={SIAM Journal on Computing},
	volume={40},
	number={3},
	pages={827--847},
	year={2011},
	publisher={SIAM}
}

@book{Gra16,
	title={Lattice theory: special topics and applications},
	author={Gr{\"a}tzer, George and Wehrung, Friedrich},
	year={2016},
	publisher={Springer}
}

@article{Mon03,
	title={The presence of lattice theory in discrete problems of mathematical social sciences. {W}hy?},
	author={Monjardet, Bernard},
	journal={Mathematical Social Sciences},
	volume={46},
	number={2},
	pages={103--144},
	year={2003},
	publisher={Elsevier}
}

@book{Nie15,
	title={Principles of program analysis},
	author={Nielson, Flemming and Nielson, Hanne R and Hankin, Chris},
	year={2015},
	publisher={Springer}
}

@article{Nou99,
	title={A fast algorithm for building lattices},
	author={Nourine, Lhouari and Raynaud, Olivier},
	journal={Information processing letters},
	volume={71},
	number={5-6},
	pages={199--204},
	year={1999},
	publisher={Elsevier}
}

@article{Cas93,
	title={Efficient handling of multiple inheritance hierarchies},
	author={Caseau, Yves},
	journal={ACM SIGPLAN Notices},
	volume={28},
	number={10},
	pages={271--287},
	year={1993},
	organization={ACM}
}

@inproceedings{Kra97,
	title={Near optimal hierarchical encoding of types},
	author={Krall, Andreas and Vitek, Jan and Horspool, R Nigel},
	booktitle={European Conference on Object-Oriented Programming},
	pages={128--145},
	year={1997},
	organization={Springer}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: Lazy Search Trees
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%


@book{overmars1983design,
	title={The design of dynamic data structures},
	author={Overmars, Mark H},
	volume={156},
	year={1983},
	publisher={Springer Science \& Business Media}
}

@inproceedings{Mortensen05,
	Author = {Christian W. Mortensen and Seth Pettie},
	Booktitle = {Workshop on Algorithms and Data Structures (WADS)},
	Title = {The Complexity of Implicit and Space Efficient Priority Queues},
	doi = {10.1007/11534273_6},
	publisher = {Springer},
	pages = {49--60},
	Year = {2005}
}

@inproceedings{Brodal09,
	Author = {Gerth St{\o}lting Brodal},
	Booktitle = {Space-Efficient Data Structures, Streams, and Algorithms},
	doi = {10.1007/978-3-642-40273-9_11},
	year = {2013},
	publisher = {Springer},
	pages = {150--163},
	Title = {A Survey on Priority Queues}}

@article{Edelkamp12,
	Author = {Stefan Edelkamp and Amr Elmasry and Jyrki Katajainen},
	Journal = {Journal of Discrete Algorithms},
	doi = {10.1016/j.jda.2012.04.010},
	month = oct,
	publisher = {Elsevier},
	pages = {187--205},
	Volume = {16},
	Title = {The weak-heap data structure: Variants and applications},
	Year = {2012}}

@article{Badoiu06,
	doi = {10.1016/j.tcs.2007.03.002},
	month = aug,
	publisher = {Elsevier},
	volume = {382},
	number = {2},
	pages = {86--96},
	author = {Mihai B{\u{a}}doiu and Richard Cole and Erik D. Demaine and John Iacono},
	title = {A unified access bound on comparison-based dynamic dictionaries},
	journal = {Theoretical Computer Science},
	Year = {2007}}

@inproceedings{Iacono01,
	Author = {John Iacono},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Pages = {516--522},
	Title = {Alternatives to splay trees with {$O(\log n)$} worst-case access time},
	publisher = {SIAM},
	Year = {2001}}

@article{Aggarwal91,
	Author = {Alok Aggarwal and Prabhakar Raghavan},
	Journal = {Information Processing Letters},
	Volume = {40},
	doi = {10.1016/0020-0190(91)90164-d},
	month = nov,
	publisher = {Elsevier},
	pages = {119--122},
	Number = {3},
	Title = {Deferred data structure for the nearest neighbor problem},
	Year = {1991}}

@article{Ar02,
	Author = {Sigal Ar and Gil Montag and Ayellet Tal},
	Journal = {Computer Graphics Forum},
	Volume = {21},
	Number = {3},
	doi = {10.1111/1467-8659.t01-1-00586},
	month = sep,
	publisher = {Wiley},
	pages = {269--278},
	Title = {Deferred, Self-Organizing {BSP} trees},
	Year = {2002}}

@inproceedings{Gum01,
	Author = {Ben Gum and Richard Lipton},
	Booktitle = {International Conference on Data Mining (ICDM)},
	publisher = {SIAM},
	Title = {Cheaper by the Dozen: Batched Algorithms},
	doi = {10.1137/1.9781611972719.23},
	Year = {2001}}

@inproceedings{Wang06,
	Author = {Chengwen Chris Wang and Jonathan Derryberry and Daniel Dominic Sleator},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Pages = {374--383},
	publisher = {SIAM},
	Title = {$O(\log \log n)$-Competititve Dynamic Binary Search Trees},
	Year = {2006}}

@report{Navarro08,
	author = {Gonzalo Navarro and Rodrigo Paredes},
	title = {Quickheaps: Simple, Efficient, and Cache-Oblivious},
	institute = {Universidad de Chile},
	year = {2008}
}
@article{Navarro10,
	doi = {10.1007/s00453-010-9400-6},
	year = {2010},
	month = mar,
	publisher = {Springer},
	volume = {57},
	number = {4},
	pages = {585--620},
	author = {Gonzalo Navarro and Rodrigo Paredes},
	title = {On Sorting,  Heaps,  and Minimum Spanning Trees},
	journal = {Algorithmica}
}

@inproceedings{Paredes06,
	Author = {Rodrigo Parades and Gonzalo Navarro},
	Booktitle = {Workshop on Algorithm Engineering and Experiments (ALENEX)},
	doi = {10.1137/1.9781611972863.16},
	month = jan,
	publisher = {SIAM},
	Title = {Optimal Incremental Sorting},
	Year = {2006}}


@inproceedings{Regla15,
	Author = {Erik Regla and Rodrigo Paredes},
	Booktitle = {Conference of the Chilean Computer Science Society (SCCC)},
	doi = {10.1109/sccc.2015.7416566},
	month = nov,
	publisher = {{IEEE}},
	Title = {Worst-Case Optimal Incremental Sorting},
	Year = {2015}}


@inproceedings{Aydin15,
	Author = {Ahmet Arif Aydin and Kenneth M. Anderson},
	Booktitle = {International Conference on Big Data Computing Service and Applications},
	doi = {10.1109/bigdataservice.2015.35},
	publisher = {{IEEE}},
	Title = {Incremental Sorting for Large Dynamic Data Sets},
	Year = {2015}}

@book{Knuth73,
	Author = {Donald Knuth},
	Date-Added = {2020-05-27 17:44:07 -0400},
	Date-Modified = {2020-05-27 17:46:16 -0400},
	Publisher = {Addison-Wesley},
	Title = {The Art of Computer Programming},
	Volume = {3, Sorting and Searching},
	Year = {1973}}

@article{Cunto89,
	Author = {Walter Cunto and J. Ian Munro},
	Journal = {Journal of the ACM},
	Number = {2},
	Pages = {270--279},
	Title = {Average Case Selection},
	Volume = {36},
	doi = {10.1145/62044.62047},
	Year = {1989}}

@article{Hoare61,
	Author = {C. A. R. Hoare},
	Journal = {Communications of the ACM},
	Number = {7},
	Pages = {321--322},
	Title = {Algorithm 65: Find},
	Volume = {4},
	Year = {1961}}

@article{Blum73,
	Author = {Manuel Blum and Robert W. Floyd and Vaughan Pratt and Ronald L. Rivest and Robert E. Tarjan},
	Date-Added = {2020-04-15 00:47:26 -0400},
	Date-Modified = {2020-04-15 00:49:34 -0400},
	Journal = {Journal of Computer and System Sciences},
	Number = {4},
	Pages = {448--461},
	Title = {Time bounds for selection},
	Volume = {7},
	Year = {1973}}

@inproceedings{Fagin01,
	Author = {Ronald Fagin and Amnon Lotem and Moni Naor},
	Booktitle = {Symposium on Principles of Database Systems (PODS)},
	Date-Added = {2020-04-14 21:29:06 -0400},
	Date-Modified = {2020-04-14 21:31:27 -0400},
	Title = {Optimal aggregation algorithms for middleware},
	Year = {2001}}

@article{Fagin2003,
	doi = {10.1016/s0022-0000(03)00026-6},
	year = {2003},
	month = jun,
	publisher = {Elsevier},
	volume = {66},
	number = {4},
	pages = {614--656},
	author = {Ronald Fagin and Amnon Lotem and Moni Naor},
	title = {Optimal aggregation algorithms for middleware},
	journal = {Journal of Computer and System Sciences}
}

@article{Dumitrescu19,
	Author = {Adrian Dumitrescu},
	Date-Added = {2020-04-14 00:22:19 -0400},
	Date-Modified = {2020-04-14 00:23:12 -0400},
	Journal = {Algorithms},
	publisher = {MDPI},
	doi = {10.3390/a12030058},
	Number = {3},
	Title = {A Selectable Sloppy Heap},
	Volume = {12},
	pages = {58},
	Year = {2019}}

@inproceedings{Brodal03,
	Author = {Gerth St{\o}lting Brodal and Rolf Fagerberg},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2020-04-09 17:52:19 -0400},
	Date-Modified = {2020-04-09 17:55:26 -0400},
	Pages = {546--554},
	publisher = {SIAM},
	Title = {Lower bounds for external memory dictionaries},
	Year = {2003}}



@misc{Munro18,
	Author = {J. Ian Munro},
	Howpublished = {personal communication},
	Year = {2018}}

@article{Hansen15,
	Author = {Thomas Dueholm Hansen and Haim Kaplan and Robert E. Tarjan and Uri Zwick},
	Booktitle = {International},
	Date-Added = {2020-04-02 19:19:41 -0400},
	Date-Modified = {2020-04-02 19:21:40 -0400},
	Journal = {ACM Transactions on Algorithms},
	Number = {3},
	Title = {Hollow Heaps},
	Volume = {13},
	pages = {1--27},
	doi = {10.1145/3093240},
	Year = {2017}}


@inproceedings{Levy19,
	Author = {Caleb Levy and Robert E. Tarjan},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2020-04-02 18:51:33 -0400},
	Date-Modified = {2020-04-02 18:52:55 -0400},
	Pages = {1311--1330},
	publisher = {SIAM},
	doi = {10.1137/1.9781611975482.80},
	Title = {A new path from splay to dynamic optimality},
	Year = {2019}}


@inproceedings{Chalermsook15,
	Author = {Parinya Chalermsook and Mayank Goswami and L{\'a}szl{\'o} Kozma and Kurt Mehlhorn and Thatchaphol Saranurak},
	Booktitle = {Symposium on Foundations of Computer Science (FOCS)},
	Pages = {410-423},
	Title = {Pattern-Avoiding Access in Binary Search Trees},
	doi = {10.1109/focs.2015.32},
	publisher = {{IEEE}},
	Year = {2015}
}

@article{Kozma2019,
	doi = {10.1137/18m1195188},
	year = {2019},
	month = nov,
	publisher = {{SIAM}},
	pages = {STOC18--45--STOC18--93},
	author = {L{\'{a}}szl{\'{o}} Kozma and Thatchaphol Saranurak},
	title = {Smooth Heaps and a Dual View of Self-Adjusting Data Structures},
	journal = {{SIAM} Journal on Computing}
}



@article{Fredman84,
	doi = {10.1145/828.1884},
	Date-Added = {2019-11-05 14:34:49 -0500},
	Date-Modified = {2019-11-05 14:37:32 -0500},
	year = {1984},
	month = jun,
	volume = {31},
	number = {3},
	pages = {538--544},
	author = {Michael L. Fredman and J{\'{a}}nos Koml{\'{o}}s and Endre Szemer{\'{e}}di},
	title = {Storing a Sparse Table with {$O(1)$} Worst Case Access Time},
	journal = {Journal of the {ACM}}
}

@article{Pagh04,
	Author = {Rasmus Pagh and Flemming Friche Rodler},
	Date-Added = {2019-11-05 14:31:05 -0500},
	Date-Modified = {2019-11-05 14:31:39 -0500},
	Journal = {Journal of Algorithms},
	Number = {2},
	Pages = {122-144},
	Title = {Cuckoo Hashing},
	Volume = {51},
	Year = {2004}}

@article{McCreight85,
	Author = {Edward McCreight},
	Date-Added = {2019-11-05 14:23:30 -0500},
	Date-Modified = {2019-11-05 14:24:13 -0500},
	Journal = {SIAM Journal on Scientific Computing},
	Number = {2},
	Pages = {257-276},
	Title = {Priority search trees},
	Volume = {14},
	Year = {1985}}

@article{ONeil96,
	Author = {Patrick O'Neil and Edward Cheng and Dieter Gawlick and Elizabeth O'Neil},
	Date-Added = {2019-11-04 18:56:02 -0500},
	Date-Modified = {2019-11-04 18:57:09 -0500},
	Journal = {Acta Informatica},
	Number = {4},
	Pages = {351-385},
	Title = {The log-structured merge-tree ({LSM}-tree)},
	Volume = {33},
	Year = {1996}}

@article{Cole2000b,
	Author = {Richard Cole},
	Date-Added = {2019-11-04 16:45:42 -0500},
	Date-Modified = {2019-11-04 16:46:30 -0500},
	Journal = {SIAM Journal on Computing},
	Number = {1},
	Pages = {44-85},
	Title = {On the Dynamic Finger Conjecture for Splay Trees. Part {II}: The Proof},
	Volume = {30},
	Year = {2000}}

@article{Cole2000a,
	Author = {Richard Cole and Bud Mishra and Jeanette Schmidt and Alan Siegel},
	Date-Added = {2019-11-04 16:44:18 -0500},
	Date-Modified = {2019-11-04 16:45:35 -0500},
	Journal = {SIAM Journal on Computing},
	Number = {1},
	Pages = {1-43},
	Title = {On the Dynamic Finger Conjecture for Splay Trees. Part {I}: Splay Sorting $\log n$-Block Sequences},
	Volume = {30},
	Year = {2000}}

@article{Elmasry04,
	Author = {Amr Elmasry},
	Date-Added = {2019-11-04 16:42:57 -0500},
	Date-Modified = {2019-11-04 16:43:53 -0500},
	Journal = {Theoretical Computer Science},
	Number = {3},
	Pages = {459-466},
	Title = {On the sequential access theorem and deque conjecture for splay trees},
	Volume = {314},
	Year = {2004}}

@article{Bentley76,
	Author = {Jon L. Bentley and Andrew C. Yao},
	Date-Added = {2019-11-04 00:42:44 -0500},
	Date-Modified = {2019-11-04 00:43:35 -0500},
	Journal = {Information Processing Letters},
	Title = {An almost optimal algorithm for unbounded searching},
	Year = {1976}}

@inproceedings{Shao94,
	Author = {Zhong Shao and John H. Reppy and Andrew W. Appel},
	Booktitle = {Proceedings of the 1994 ACM conference on LISP and functional programming},
	Date-Added = {2019-11-03 13:29:42 -0500},
	Date-Modified = {2019-11-03 13:30:52 -0500},
	Title = {Unrolling lists},
	Year = {1994}}

@article{Tarjan85,
	Author = {Robert E. Tarjan},
	Date-Added = {2019-11-02 23:17:34 -0400},
	Date-Modified = {2019-11-02 23:19:02 -0400},
	Journal = {SIAM Journal on Algebraic Discrete Methods},
	Number = {2},
	Title = {Amortized Computational Complexity},
	Volume = {6},
	Year = {1985}}

@article{Bent85,
	Author = {Samuel W. Bent and Daniel D. Selator and Robert E. Tarjan},
	Date-Added = {2019-10-31 10:56:47 -0400},
	Date-Modified = {2019-10-31 10:57:56 -0400},
	Journal = {SIAM Journal on Computing},
	Number = {3},
	Pages = {545-568},
	Title = {Biased Search Trees},
	Volume = {14},
	Year = {1985}}

@inproceedings{Barbay13,
	Author = {J{\'e}r{\'e}my Barbay and Ankur Gupta and Seungbum Jo and Rao Satti, Srinivasa and Jonathan Sorenson},
	Booktitle = {European Symposium on Algorithms (ESA)},
	doi = {10.1007/978-3-642-40450-4_10},
	publisher = {Springer},
	pages = {109--120},
	Date-Added = {2019-10-29 15:30:05 -0400},
	Date-Modified = {2019-10-29 15:35:30 -0400},
	Title = {Theory and Implementation of Online Multiselection Algorithms},
	Year = {2013}}



@article{Barbay16b,
	Author = {J{\'e}r{\'e}my Barbay},
	Date-Modified = {2019-10-29 15:28:53 -0400},
	Journal = {arXiv},
	Title = {Optimal Prefix Free Codes With Partial Sorting},
	Year = {2016}}

@article{Barbay2019,
	doi = {10.3390/a13010012},
	year = {2019},
	month = dec,
	publisher = {{MDPI}},
	volume = {13},
	number = {1},
	pages = {12},
	author = {J{\'{e}}r{\'{e}}my Barbay},
	title = {Optimal Prefix Free Codes with Partial Sorting},
	journal = {Algorithms}
}

@article{Dobkin81,
	Author = {David Dobkin and J. Ian Munro},
	Date-Added = {2019-10-29 15:06:45 -0400},
	Date-Modified = {2019-10-29 15:07:41 -0400},
	Journal = {Journal of the Association for Computing Machinery},
	Number = {3},
	Pages = {454-461},
	Title = {Optimal Time Minimal Space Selection Algorithms},
	Volume = {28},
	Year = {1981}}

@inproceedings{Barbay17,
	Author = {J{\'e}r{\'e}my Barbay and Carlos Ochoa and Srinivasa Rao Satti},
	Booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM)},
	Date-Added = {2019-10-29 13:35:23 -0400},
	Date-Modified = {2019-10-29 13:36:30 -0400},
	doi =		{10.4230/LIPIcs.CPM.2017.31},
	volume =	{78},
	publisher =	{Schloss Dagstuhl},
	series =	{LIPIcs},
	Title = {Synergistic Solutions on MultiSets},
	Year = {2017}}


@article{Brodal11,
	Author = {Gerth St{\o}lting Brodal and Beat Gfeller and Allan Gr{\o}nlund J{\o}rgensen and Peter Sanders},
	Date-Added = {2019-10-29 13:15:10 -0400},
	Date-Modified = {2019-10-29 13:16:11 -0400},
	Journal = {Theoretical Computer Science},
	Number = {24},
	Pages = {2588-2601},
	Title = {Towards optimal range medians},
	Volume = {412},
	Year = {2011}}

@article{Sigal00,
	Author = {Sigal Ar and Bernhard Chazelle and Ayellet Tal},
	Date-Added = {2019-10-29 13:11:34 -0400},
	Date-Modified = {2019-10-29 13:12:47 -0400},
	Journal = {Computational Geometry},
	Number = {1-3},
	Pages = {91-102},
	Title = {Self-customized {BSP} trees for collision detection},
	Volume = {15},
	Year = {2000}}

@article{Borodin81,
	Author = {A. Borodin and L. J. Guibas and N. A. Lynch and A. C. Yao},
	Date-Added = {2019-10-29 13:07:51 -0400},
	Date-Modified = {2019-10-29 13:08:49 -0400},
	Journal = {Information Processing Letters},
	Number = {2},
	Pages = {71-75},
	Title = {Efficient searching using partial ordering},
	Volume = {12},
	Year = {1981}}

@phdthesis{Smid89,
	Author = {Michiel Smid},
	Date-Added = {2019-10-27 18:05:37 -0400},
	Date-Modified = {2019-10-27 18:07:16 -0400},
	School = {University of Amsterdam},
	Title = {Dynamic Data Structures on Multiple Storage Media},
	Year = {1989}}

@article{Karp88,
	Author = {Richard M. Karp and Rajeev Motwani and Prabhakar Raghavan},
	Date-Added = {2019-10-27 17:36:27 -0400},
	Date-Modified = {2019-10-27 17:37:29 -0400},
	Journal = {SIAM Journal on Computing},
	Number = {5},
	Pages = {883-902},
	Title = {Deferred Data Structuring},
	Volume = {17},
	Year = {1988}}

@inproceedings{Barbay15,
	Author = {J{\'{e}}r{\'{e}}my Barbay and Ankur Gupta and Rao Satti, Srinivasa and Jon Sorenson},
	Booktitle = {WALCOM: Algorithms and Computation},
	Date-Added = {2019-10-27 17:06:19 -0400},
	Date-Modified = {2019-10-27 17:07:42 -0400},
	doi = {10.1007/978-3-319-15612-5_18},
	pages = {199--209},
	publisher = {Springer},
	Title = {Dynamic Online Multiselection in Internal and External Memory},
	Year = {2015}}



@article{Frederickson93,
	Author = {Greg N. Frederickson},
	Date-Added = {2019-10-27 15:57:18 -0400},
	Date-Modified = {2019-10-27 15:57:59 -0400},
	doi = {10.1006/inco.1993.1030},
	Journal = {Information and Computation},
	volume = {104},
	number = {2},
	publisher = {Elsevier},
	pages = {197--214},
	Title = {An Optimal Algorithm for Selection in a Min-Heap},
	Year = {1993}}



@inproceedings{Brodal96,
	Author = {Gerth St{\o}lting Brodal},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2019-10-25 13:24:35 -0400},
	Date-Modified = {2019-10-25 13:25:43 -0400},
	Title = {Worst-case efficient priority queues},
	publisher = {SIAM},
	Year = {1996}}

@article{Haeupler11,
	Author = {Bernhard Haeupler and Siddhartha Sen and Robert E. Tarjan},
	Date-Added = {2019-10-25 13:21:47 -0400},
	Date-Modified = {2019-10-25 13:23:11 -0400},
	Journal = {SIAM Journal on Computing},
	Number = {6},
	Pages = {1463-1485},
	Title = {Rank-Pairing Heaps},
	Volume = {40},
	Year = {2011}}

@inproceedings{Elmasry09,
	Author = {Amr Elmasry},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2019-10-25 13:20:01 -0400},
	publisher = {SIAM},
	Date-Modified = {2019-10-25 13:21:03 -0400},
	doi = {10.1137/1.9781611973068.52},
	Title = {Pairing heaps with {$O(\log \log n)$} decrease cost},
	Year = {2009}}



@article{Fredman86,
	Author = {Michael L. Fredman and Robert Sedgewick and Daniel D. Sleator and Robert E. Tarjan},
	Date-Added = {2019-10-25 13:18:42 -0400},
	Date-Modified = {2019-10-25 13:19:39 -0400},
	Journal = {Algorithmica},
	Number = {1},
	Pages = {111-129},
	Title = {The pairing heap: A new form of self-adjusting heap},
	Volume = {1},
	Year = {1986}}

@inproceedings{Bose13,
	Author = {Prosenjit Bose and John Howat and Pat Morin},
	Booktitle = {Space-Efficient Data Structures, Streams, and Algorithms},
	doi = {10.1007/978-3-642-40273-9_10},
	publisher = {Springer},
	pages = {133--149},
	Title = {A History of Distribution-Sensitive Data Structures},
	Year = {2009}}


@inproceedings{Chan09,
	Author = {Timothy M. Chan},
	Booktitle = {Space-Efficient Data Structures, Streams, and Algorithms},
	Date-Added = {2019-10-25 13:16:42 -0400},
	Date-Modified = {2019-10-25 13:18:19 -0400},
	doi = {10.1007/978-3-642-40273-9_3},
	pages = {27--32},
	publisher = {Springer},
	Title = {Quake Heaps: A Simple Alternative to {Fibonacci} Heaps},
	Year = {2009}}


@inproceedings{Brodal12,
	author = {Gerth St{\o}lting Brodal and George Lagogiannis and Robert E. Tarjan},
	Booktitle = {Symposium on Theory of Computing (STOC)},
	Date-Added = {2019-10-25 13:11:44 -0400},
	Date-Modified = {2019-10-25 13:16:16 -0400},
	doi = {10.1145/2213977.2214082},
	publisher = {{ACM}},
	Title = {Strict {Fibonacci} heaps},
	Year = {2012}}


@article{Fredman87,
	Author = {Michael Fredman and Robert E. Tarjan},
	Date-Added = {2019-10-25 13:06:23 -0400},
	Date-Modified = {2019-10-25 13:07:40 -0400},
	Journal = {Journal of the Association for Computing Machinery},
	Number = {3},
	Pages = {596-615},
	Title = {Fibonacci heaps and their uses in improved network optimization algorithms},
	Volume = {34},
	Year = {1987}}

@article{Brown78,
	Author = {Mark R. Brown},
	Date-Added = {2019-10-25 13:01:42 -0400},
	Date-Modified = {2019-10-25 13:02:30 -0400},
	Journal = {SIAM Journal on Computing},
	Number = {3},
	Pages = {298-319},
	Title = {Implementation and Analysis of Binomial Queue Algorithms},
	Volume = {7},
	Year = {1978}}

@article{Vuillemin78,
	Author = {Jean Vuillemin},
	Date-Added = {2019-10-25 13:00:22 -0400},
	Date-Modified = {2019-10-25 13:02:54 -0400},
	Journal = {Communications of the ACM},
	Number = {4},
	Pages = {309-315},
	Title = {A data structure for manipulating priority queues},
	Volume = {21},
	Year = {1978}}

@article{Wilber89,
	Author = {Robert E. Wilber},
	Date-Added = {2019-10-25 01:06:21 -0400},
	Date-Modified = {2019-10-25 01:07:04 -0400},
	Journal = {Siam Journal of Computing},
	Number = {1},
	Pages = {56-69},
	Title = {Lower bounds for accessing binary search trees with rotations},
	Volume = {18},
	Year = {1989}}

@inproceedings{Iacono16,
	Author = {John Iacono and Stefan Langerman},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2019-10-25 01:00:49 -0400},
	Date-Modified = {2019-10-25 01:01:46 -0400},
	doi = {10.1137/1.9781611974331.ch49},
	publisher = {SIAM},
	Title = {Weighted dynamic finger in binary search trees},
	Year = {2016}}


@article{Demaine07,
	Author = {Erik D. Demaine and Dion Harmon and John Iacono and Mihai Patrascu},
	Date-Added = {2019-10-25 00:59:05 -0400},
	Date-Modified = {2019-10-25 01:00:15 -0400},
	Journal = {Siam Journal of Computing},
	Number = {1},
	Pages = {240-251},
	Title = {Dynamic optimality--almost.},
	Volume = {37},
	Year = {2007}}

@inproceedings{Demaine09,
	Author = {Erik D. Demaine and Dion Harmon and John Iacono and Daniel Kane and Mihai Patrascu},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2019-10-25 00:58:09 -0400},
	publisher = {SIAM},
	Date-Modified = {2019-10-25 01:10:10 -0400},
	Title = {The geometry of binary search trees},
	pages = {496--505},
	Year = {2009}}

@article{Bose19,
	Author = {Prosenjit Bose and Jean Cardinal and John Iacono and Grigorios Koumoutsos and Stefan Langerman},
	Date-Added = {2019-10-25 00:44:26 -0400},
	Date-Modified = {2019-10-25 00:49:34 -0400},
	Journal = {arXiv},
	Title = {Competitive Online Search Trees on Trees},
	Year = {2019}}
@incollection{Bose2020,
	doi = {10.1137/1.9781611975994.115},
	year = {2020},
	month = jan,
	publisher = {Society for Industrial and Applied Mathematics},
	pages = {1878--1891},
	author = {Prosenjit Bose and Jean Cardinal and John Iacono and Grigorios Koumoutsos and Stefan Langerman},
	title = {Competitive Online Search Trees on Trees},
	booktitle = {Symposium on Discrete Algorithms (SODA)}
}

@article{Allen78,
	Author = {Brian Allen and Ian Munro},
	Date-Added = {2019-10-25 00:25:03 -0400},
	Date-Modified = {2019-10-25 00:25:45 -0400},
	doi = {10.1145/322092.322094},
	volume = {25},
	number = {4},
	pages = {526--535},
	Journal = {Journal of the ACM},
	Title = {Self-Organizing Binary Search Trees},
	Year = {1978}}


@article{Bentley75,
	Author = {Jon L. Bentley},
	Date-Added = {2019-10-25 00:03:34 -0400},
	Date-Modified = {2019-10-25 00:04:53 -0400},
	Journal = {Communications of the ACM},
	Title = {Multidimensional binary search trees used for associative searching},
	Year = {1975}}

@techreport{McCreight80,
	Author = {E. M. McCreight},
	Date-Added = {2019-10-25 00:00:08 -0400},
	Date-Modified = {2019-10-25 00:01:30 -0400},
	Institution = {Xerox Palo Alto Research Center},
	Title = {Efficient algorithms for enumerating intersecting intervals and rectangles},
	Year = {1980}}

@techreport{Edelsbrunner80,
	Author = {H. Edelsbrunner},
	Date-Added = {2019-10-24 23:44:10 -0400},
	Date-Modified = {2019-10-24 23:58:51 -0400},
	Institution = {Tech. Univ. Graz},
	Title = {Dynamic data structures for orthogonal intersection queries},
	Year = {1980}}

@techreport{Bentley77,
	Author = {Jon L. Bentley},
	Date-Added = {2019-10-24 23:41:48 -0400},
	Date-Modified = {2019-10-24 23:42:41 -0400},
	Institution = {Carnegie Mellon University},
	Title = {Solutions to Klee's rectangle problems},
	Year = {1977}}

@article{Seidel96,
	Author = {Raimund Seidel and Cecilia R. Aragon},
	Date-Added = {2019-10-24 23:25:12 -0400},
	Date-Modified = {2019-10-24 23:26:01 -0400},
	Journal = {Algorithmica},
	Title = {Randomized search trees},
	Year = {1996}}

@inproceedings{Galperin93,
	Author = {Igal Galperin and Ronald L. Rivest},
	Booktitle = {Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Date-Added = {2019-10-24 23:22:00 -0400},
	Date-Modified = {2019-10-24 23:24:08 -0400},
	Title = {Scapegoat trees},
	Year = {1993}}

@inproceedings{Andersson89,
	Author = {Arne Andersson},
	Booktitle = {Workshop on Algorithms and Data Structures},
	Date-Added = {2019-10-24 23:20:50 -0400},
	Date-Modified = {2019-10-24 23:21:39 -0400},
	Title = {Improving partial rebuilding by using simple balance criteria},
	Year = {1989}}

@article{Bayer72,
	Author = {R. Bayer and E. M. McCreight},
	Date-Added = {2019-10-24 23:16:48 -0400},
	Date-Modified = {2019-10-24 23:17:34 -0400},
	Journal = {Acta Informatica},
	Number = {3},
	Pages = {173-189},
	Title = {Organization and maintenance of large ordered indexes},
	Volume = {1},
	Year = {1972}}

@article{Bentley79,
	Author = {Jon Louis Bentley},
	Date-Added = {2019-10-23 16:37:58 -0400},
	Date-Modified = {2019-10-23 16:39:52 -0400},
	Journal = {Information Processing Letters},
	Number = {5},
	Pages = {244-251},
	Title = {Decomposable searching problems},
	Volume = {8},
	Year = {1979}}

@article{Sleator85,
	Author = {Daniel D. Sleator and Robert E. Tarjan},
	Date-Added = {2019-10-23 16:23:28 -0400},
	Date-Modified = {2019-10-23 16:24:19 -0400},
	Journal = {Journal of the ACM},
	Number = {3},
	Pages = {652-686},
	Title = {Self-Adjusting Binary Seach Trees},
	Volume = {32},
	Year = {1985}}

@article{Bayer72b,
	Author = {Rudolf Bayer},
	Date-Added = {2019-10-23 16:21:18 -0400},
	Date-Modified = {2019-10-24 23:29:14 -0400},
	Journal = {Acta Informatica},
	Number = {4},
	Pages = {290-306},
	Title = {Symmetric binary B-Trees: Data structure and maintenance algorithms},
	Volume = {1},
	Year = {1972}}

@article{Williams64,
	Author = {J. W. J. Williams},
	Date-Added = {2019-10-23 15:41:58 -0400},
	Date-Modified = {2019-10-23 15:43:50 -0400},
	Journal = {Communications of the ACM},
	Number = {6},
	Pages = {347-348},
	Title = {Algorithm 232 - Heapsort},
	Volume = {7},
	Year = {1964}}

@article{Adelson62,
	Author = {Georgy Adelson-Velsky and Evgenii Landis},
	Date-Added = {2019-10-23 13:24:30 -0400},
	Date-Modified = {2019-10-23 13:25:56 -0400},
	Journal = {Proceedings of the USSR Academy of Sciences},
	Pages = {263-266},
	Title = {An algorithm for the organization of information},
	Volume = {146},
	Year = {1962}}

@article{Booth60,
	Author = {A. D. Booth and A. J. T. Colin},
	Date-Added = {2019-10-23 13:17:56 -0400},
	Date-Modified = {2019-10-23 13:18:40 -0400},
	Journal = {Information and Control},
	Pages = {327-334},
	Title = {On the efficiency of a new method of dictionary construction},
	Volume = {3},
	Year = {1960}}

@article{Windley60,
	Author = {P. F. Windley},
	Date-Added = {2019-10-23 13:16:12 -0400},
	Date-Modified = {2019-10-23 13:16:59 -0400},
	Journal = {The Computer Journal},
	Pages = {84},
	Title = {Trees, Forests, and Rearranging},
	Volume = {3},
	Year = {1960}}

@article{Hibbard62,
	Author = {T. Hibbard},
	Date-Added = {2019-10-23 13:13:42 -0400},
	Date-Modified = {2019-10-23 13:15:53 -0400},
	Journal = {Assoc. Comp. Mach.},
	Pages = {13},
	Title = {Some Combinatorial Properties of Certain Trees},
	Volume = {9},
	Year = {1962}}

@article{Douglas59,
	Author = {A. S. Douglas},
	Date-Added = {2019-10-23 12:36:42 -0400},
	Date-Modified = {2019-10-23 12:38:03 -0400},
	Journal = {The Computer Journal},
	Pages = {1},
	Title = {Techniques for the Recording of, and Reference to data in a Computer},
	Volume = {2},
	Year = {1959}}

@book{CLRS,
	Author = {Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein},
	Publisher = {The MIT Press},
	Title = {Introduction to Algorithms},
	Year = {2009}}

@inproceedings{KMMS,
	Author = {Kaligosi, Kanela and Mehlhorn, Kurt and Munro, J. Ian and Sanders, Peter},
	Booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)},
	Pages = {103--114},
	doi = {10.1007/11523468_9},
	Publisher = {Springer},
	Title = {Towards Optimal Multiple Selection},
	Year = {2005}}

@article{CHING90,
	Author = {Yu-Tai Ching and Kurt Mehlhorn and Michiel H.M. Smid},
	Issn = {0020-0190},
	Journal = {Information Processing Letters},
	Number = {1},
	Pages = {37 - 40},
	Title = {Dynamic deferred data structuring},
	Volume = {35},
	Year = {1990}}

@article{BARBAY16,
	Author = {J{\'e}r{\'e}my Barbay and Ankur Gupta and Srinivasa Rao Satti and Jon Sorenson},
	Issn = {1570-8667},
	Journal = {Journal of Discrete Algorithms},
	Pages = {3--17},
	Title = {Near-optimal online multiselection in internal and external memory},
	Volume = {36},
	Year = {2016}}

@inproceedings{GOLIN18,
	Author = {Mordecai J. Golin and John Iacono and Stefan Langerman and J. Ian Munro and Yakov Nekrich},
	Booktitle = {ESA},
	Title = {Dynamic Trees with Almost-Optimal Access Cost},
	Year = {2018}}

@article{BLUM80,
	Author = {Norbert Blum and Kurt Mehlhorn},
	Issn = {0304-3975},
	Journal = {Theoretical Computer Science},
	Number = {3},
	Pages = {303 - 320},
	Title = {On the average number of rebalancing operations in weight-balanced trees},
	Volume = {11},
	Year = {1980}}

@inproceedings{NIEVER72,
	Acmid = {804906},
	Address = {New York, NY, USA},
	Author = {Nievergelt, J. and Reingold, E. M.},
	Booktitle = {Proceedings of the Fourth Annual ACM Symposium on Theory of Computing},
	Numpages = {6},
	Pages = {137--142},
	Publisher = {ACM},
	Series = {STOC '72},
	Title = {Binary Search Trees of Bounded Balance},
	Year = {1972}}

@inproceedings{Cardinal09,
	Acmid = {1536430},
	Address = {New York, NY, USA},
	Author = {Cardinal, Jean and Fiorini, Samuel and Joret, Gwena\"{e}l and Jungers, Rapha\"{e}l M. and Munro, J. Ian},
	Booktitle = {Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing},
	Doi = {10.1145/1536414.1536430},
	Isbn = {978-1-60558-506-2},
	Keywords = {graph entropy, partial order},
	Location = {Bethesda, MD, USA},
	Numpages = {8},
	Pages = {93--100},
	Publisher = {ACM},
	Series = {STOC '09},
	Title = {An Efficient Algorithm for Partial Order Production},
	Url = {http://doi.acm.org/10.1145/1536414.1536430},
	Year = {2009},
	Bdsk-Url-1 = {http://doi.acm.org/10.1145/1536414.1536430},
	Bdsk-Url-2 = {https://doi.org/10.1145/1536414.1536430}}

@article{Cardinal13,
	Author = {Cardinal, Jean and Fiorini, Samuel and Joret, Gwena{\"e}l and Jungers, Rapha{\"e}l M. and Munro, J. Ian},
	Day = {01},
	Doi = {10.1007/s00493-013-2821-5},
	Issn = {1439-6912},
	Journal = {Combinatorica},
	Month = {Dec},
	Number = {6},
	Pages = {655--697},
	Title = {Sorting under partial information (without the ellipsoid algorithm)},
	Url = {https://doi.org/10.1007/s00493-013-2821-5},
	Volume = {33},
	Year = {2013},
	Bdsk-Url-1 = {https://doi.org/10.1007/s00493-013-2821-5}}

@incollection{Fox2011,
	title = {Upper Bounds for Maximally Greedy Binary Search Trees},
	doi = {10.1007/978-3-642-22300-6_35},
	year = {2011},
	publisher = {Springer Berlin Heidelberg},
	pages = {411--422},
	author = {Kyle Fox},
	booktitle = {Lecture Notes in Computer Science}
}

@article{Sedgewick1977a,
	title = {Quicksort with Equal Keys},
	author = {Sedgewick, Robert},
	journal = {SIAM Journal on Computing},
	number = {2},
	pages = {240--267},
	publisher = {SIAM},
	volume = {6},
	year = {1977}
}

@article{Sedgewick1978,
	title = {Implementing {Quicksort} programs},
	author = {Sedgewick, Robert},
	journal = {Communications of the {ACM}},
	keywords = {algorithms,analysis,code optimization,cr categories,phrases,quicksort,sorting},
	number = {10},
	pages = {847--857},
	publisher = {ACM Press},
	volume = {21},
	year = {1978}
}

@article{FloydRivest1975,
	title = {Expected time bounds for selection},
	author = {Floyd, Robert W. and Rivest, Ronald L.},
	doi = {10.1145/360680.360691},
	journal = {Communications of the ACM},
	number = {3},
	pages = {165--172},
	volume = {18},
	year = {1975}
}

@article{PostmusKanTimmer1983,
	doi = {10.1145/182.358440},
	year = {1983},
	month = nov,
	publisher = {Association for Computing Machinery ({ACM})},
	volume = {26},
	number = {11},
	pages = {878--881},
	author = {J. T. Postmus and A. H.G. Rinnooy Kan and G. T. Timmer},
	title = {An efficient dynamic selection method},
	journal = {Communications of the {ACM}}
}

@article{Kiwiel2005,
	doi = {10.1016/j.tcs.2005.06.032},
	year = {2005},
	month = nov,
	publisher = {Elsevier {BV}},
	volume = {347},
	number = {1-2},
	pages = {214--238},
	author = {Krzysztof C. Kiwiel},
	title = {On Floyd and Rivest's {SELECT} algorithm},
	journal = {Theoretical Computer Science}
}

@book{deBergCheongVanKreveldOvermars2008,
	author    = {Mark de Berg and
	Otfried Cheong and
	Marc J. van Kreveld and
	Mark H. Overmars},
	title     = {Computational geometry: algorithms and applications, 3rd Edition},
	publisher = {Springer},
	year      = {2008},
	isbn      = {9783540779735},
	timestamp = {Fri, 17 Jul 2020 16:12:38 +0200},
	biburl    = {https://dblp.org/rec/books/lib/BergCKO08.bib},
	bibsource = {dblp computer science bibliography, https://dblp.org}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: Space-Efficient Dynamic Range Mode
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@article{Boas77,
	Author = {P. van Emde Boas},
	Journal = {Information Processing Letters},
	Title = {Preserving order in a forest in less than logarithmic time and linear space},
	Volume = {6},
	Number = {3},
	Pages = {80-82},
	Year = {1977}}

@article{Mehlhorn90,
	Author = {Kurt Mehlhorn and Stefan N\"aher},
	Journal = {Information Processing Letters},
	Title = {Bounded ordered dictionaries in {$O(\log \log N)$} time and {$O(n)$} space},
	Volume = {35},
	Number = {4},
	Pages = {183-189},
	Year = {1990}}

@article{Krizanc05,
	Author = {Danny Krizanc and Pat Morin and Michiel Smid},
	Date-Added = {2020-02-06 15:53:17 -0500},
	Date-Modified = {2020-02-06 15:54:58 -0500},
	Journal = {Nordic Journal of Computing},
	Title = {Range Mode and Range Median Queries on Lists and Trees},
	Year = {2005}}

@inproceedings{Yuster09,
	Author = {Raphael Yuster},
	Booktitle = {20th Annual ACM-SIAM Symposium on Discrete Algorithms},
	Date-Added = {2020-02-05 18:21:11 -0500},
	Date-Modified = {2020-02-05 18:22:12 -0500},
	Pages = {950--957},
	Title = {Efficient algorithms on sets of permutations, dominance, and real-weighted APSP},
	Year = {2009}}

@article{Chan10,
	Author = {Timothy M. Chan},
	Date-Added = {2020-02-05 18:19:22 -0500},
	Date-Modified = {2020-02-05 18:20:19 -0500},
	Journal = {SIAM J. Comput.},
	Number = {5},
	Pages = {2075--2089},
	Title = {More algorithms for all-pairs shortest paths in weighted graphs},
	Volume = {39},
	Year = {2010}}

@article{Zwick02,
	Author = {Uri Zwick},
	Date-Added = {2020-02-05 18:17:19 -0500},
	Date-Modified = {2020-02-05 18:18:02 -0500},
	Journal = {J. ACM},
	Number = {3},
	Pages = {289--317},
	Title = {All pairs shortest paths using bridging sets and rectangular matrix multiplication},
	Volume = {49},
	Year = {2002}}

@inproceedings{Shoshan99,
	Author = {Avi Shoshan and Uri Zwick},
	Booktitle = {40th Annual IEEE Symposium on Foundations of Computer Science},
	Date-Added = {2020-02-05 18:14:49 -0500},
	Date-Modified = {2020-02-05 18:16:12 -0500},
	Pages = {605-615},
	Title = {All pairs shortest paths in undirected graphs with integer weights},
	Year = {1999}}

@article{Seidel95,
	Author = {Raimund Seidel},
	Date-Added = {2020-02-05 18:12:21 -0500},
	Date-Modified = {2020-02-05 18:13:43 -0500},
	Journal = {J. Comput. Syst. Sci.},
	Number = {3},
	Pages = {400-403},
	Title = {On the all-pairs-shortest-path problem in unweighted undirected graphs},
	Volume = { 51},
	Year = {1995}}

@inproceedings{Fischer71,
	Author = {Michael J Fischer and Albert R Meyer},
	Booktitle = {n 12th Annual Symposium on Switching and Automata Theory},
	Date-Added = {2020-02-05 15:38:19 -0500},
	Date-Modified = {2020-02-05 15:41:52 -0500},
	Pages = {129-131},
	Publisher = {IEEE},
	Title = {Boolean matrix multiplication and transitive closure},
	Year = {1971}}

@inproceedings{Williams20,
	Author = {Virginia Vassilevska Williams and Yinzhan Xu},
	Booktitle = {Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms},
	Date-Added = {2020-02-05 14:15:25 -0500},
	Date-Modified = {2020-02-05 14:18:48 -0500},
	Title = {Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications},
	Year = {2020}}

@article{fra08,
	Author = {Gereon Frahling and Piotr Indyk and Christian Sohler},
	Journal = {International Journal of Computational Geometry \& Applications},
	Number = {1/2},
	Pages = {3--28},
	Title = {Sampling in Dynamic Data Streams and Applications},
	Volume = {18},
	Year = {2008}}

@inproceedings{chan17,
	Author = {Chan, Timothy M and Tsakalidis, Konstantinos},
	Booktitle = {LIPIcs-Leibniz International Proceedings in Informatics},
	Organization = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik},
	Title = {Dynamic Orthogonal Range Searching on the RAM, Revisited},
	Volume = {77},
	Year = {2017}}

@inproceedings{mih10,
	Author = {P{\u{a}}tra{\c{s}}cu, Mihai and Viola, Emanuele},
	Booktitle = {Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms},
	Organization = {Society for Industrial and Applied Mathematics},
	Pages = {117--122},
	Title = {Cell-probe lower bounds for succinct partial sums},
	Year = {2010}}

@inproceedings{HMN11,
	Author = {Meng He and J. Ian Munro and Patrick K. Nicholson},
	Booktitle = {International Symposium on Algorithms and Computation},
	Date-Added = {2018-02-17 06:58:09 +0000},
	Date-Modified = {2018-02-17 06:59:20 +0000},
	Title = {Dynamic Range Selection in Linear Space},
	Year = {2011}}

@inproceedings{W12,
	Author = {Virginia Vassilevska Williams},
	Booktitle = {Proceedings of the fourty-fourth annual symposium on theory of computing},
	Date-Added = {2018-02-17 06:38:15 +0000},
	Date-Modified = {2018-02-17 06:39:09 +0000},
	Title = {Multiplying matrices faster than coppersmith-winograd},
	Year = {2012}}

@inproceedings{GJLT10,
	Author = {Mark Greve and Allan Gr{\o}nlund J{\o}rgensen and Kasper Dalgaard Larsen and Jakob Truelsen},
	Booktitle = {International Colloquium on Automata, Languages, and Programming},
	Date-Added = {2018-02-17 05:30:21 +0000},
	Date-Modified = {2018-02-17 05:43:08 +0000},
	Title = {Cell Probe Lower Bounds and Approximations for Range Mode},
	Year = {2010}}

@inproceedings{KKM13,
	Author = {Bruce M. Kapron and Valerie King and Ben Mountjoy},
	Booktitle = {Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms},
	Date-Added = {2018-02-15 17:26:35 +0000},
	Date-Modified = {2018-02-17 09:41:35 +0000},
	Pages = {1131-1142},
	Title = {Dynamic graph connectivity in polylogarithmic worst case time},
	Year = {2013}}

@article{E85,
	Author = {Edward McCreight},
	Date-Added = {2018-02-14 16:28:03 +0000},
	Date-Modified = {2018-02-14 16:28:56 +0000},
	Journal = {SIAM Journal on Scientific Computing},
	Title = {Priority Search Trees},
	Year = {1985}}

@inproceedings{P10,
	Author = {Mihai P\v{a}tra\c{s}cu},
	Booktitle = {Proceedings of the forty-second annual ACM symposium on Theory of computing},
	Date-Added = {2018-02-13 17:32:18 +0000},
	Date-Modified = {2018-02-17 09:43:19 +0000},
	Pages = {603-610},
	Title = {Towards Polynomial Lower Bounds for Dynamic Problems},
	Year = {2010}}

@inproceedings{DHMNS13,
	Author = {Stephane Durocher and Meng He and J. Ian Munro and Patrick K. Nicholson and Matthew Skala},
	Booktitle = {Information and Computation},
	Date-Added = {2018-02-13 01:16:36 +0000},
	Date-Modified = {2018-02-13 01:18:51 +0000},
	Title = {Range Majority in Constant Time and Linear Space},
	Year = {2013}}

@conference{GBT84,
	Author = {Harold N. Gabow and Jon Louis Bentley and Robert E. Tarjan},
	Booktitle = {Proceedings of the sixteenth annual ACM symposium on Theory of computing},
	Date-Added = {2018-02-13 01:00:46 +0000},
	Date-Modified = {2018-02-17 09:41:00 +0000},
	Pages = {135-143},
	Title = {Scaling and Related Techniques for Geometry Problems},
	Year = {1984}}

@conference{GK99,
	Author = {Michael T. Goodrich and John G. Koss II},
	Booktitle = {Workshop on Data Structures and Algorithms},
	Date-Added = {2018-02-09 20:26:46 +0000},
	Date-Modified = {2018-02-09 20:27:55 +0000},
	Title = {Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences},
	Year = {1999}}

@conference{D89,
	Author = {Paul F. Dietz},
	Booktitle = {Workshop on Data Structures and Algorithms},
	Date-Added = {2018-02-09 20:01:33 +0000},
	Date-Modified = {2018-02-17 09:39:56 +0000},
	Pages = {39-46},
	Title = {Optimal Algorithms for List Indexing and Subset Rank},
	Year = {1989}}

@article{C15,
	Author = {Timothy M. Chan and Stephane Durocher and Matthew Skala and Bryan T. Wilkinson},
	Date-Added = {2018-02-09 19:47:07 +0000},
	Date-Modified = {2018-02-17 09:36:16 +0000},
	Journal = {Algorithmica},
	Pages = {901-913},
	Title = {Linear-Space Data Structures for Range Minority Query in Arrays},
	Volume = {72},
	Year = {2015}}

@article{C14,
	Author = {Timothy M. Chan and Stephane Durocher and Kasper Green Larsen and Jason Morrison and Bryan T. Wilkinson},
	Date-Added = {2018-02-09 19:36:25 +0000},
	Date-Modified = {2018-02-17 09:38:09 +0000},
	Journal = {Theory of Computing Systems},
	Pages = {719-741},
	Title = {Linear-Space Data Structures for Range Mode Query in Arrays},
	Volume = {55},
	Year = {2014}}

@inproceedings{gag17,
	Author = {Gagie, Travis and He, Meng and Navarro, Gonzalo},
	Booktitle = {Data Compression Conference (DCC), 2017},
	Organization = {IEEE},
	Pages = {260--269},
	Title = {Compressed Dynamic Range Majority Data Structures},
	Year = {2017}}

@inproceedings{elm11,
	Author = {Elmasry, Amr and He, Meng and Munro, J Ian and Nicholson, Patrick K},
	Booktitle = {International Symposium on Algorithms and Computation},
	Organization = {Springer},
	Pages = {150--159},
	Title = {Dynamic range majority data structures},
	Year = {2011}}

@article{dur13,
	Author = {Durocher, Stephane and He, Meng and Munro, J Ian and Nicholson, Patrick K and Skala, Matthew},
	Journal = {Information and Computation},
	Pages = {169--179},
	Publisher = {Elsevier},
	Title = {Range majority in constant time and linear space},
	Volume = {222},
	Year = {2013}}

@inproceedings{bro11a,
	Author = {Brodal, Gerth St{\o}lting and Davoodi, Pooya and Rao, S Srinivasa},
	Booktitle = {Workshop on Algorithms and Data Structures},
	Organization = {Springer},
	Pages = {290--301},
	Title = {Path minima queries in dynamic weighted trees},
	Year = {2011}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: Faster Dynamic Range Mode
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  @article{AlonGM97,
	author    = {Noga Alon and
	Zvi Galil and
	Oded Margalit},
	title     = {On the Exponent of the All Pairs Shortest Path Problem},
	journal   = {J. Comput. Syst. Sci.},
	volume    = {54},
	number    = {2},
	pages     = {255--262},
	year      = {1997}}


@inproceedings{gall2018improved,
	title={Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor},
	author={Gall, Fran{\c{c}}ois Le and Urrutia, Florent},
	booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms},
	pages={1029--1046},
	year={2018},
	organization={SIAM}
}

@inproceedings{legallmult,
	author    = {Fran{\c{c}}ois Le Gall},
	title     = {Powers of tensors and fast matrix multiplication},
	booktitle = {International Symposium on Symbolic and Algebraic Computation, {ISSAC}
	2014, Kobe, Japan, July 23-25, 2014},
	pages     = {296--303},
	year      = {2014}}


@inproceedings{vmmult,
	author    = {Virginia {Vassilevska Williams}},
	title     = {Multiplying matrices faster than {C}oppersmith-{W}inograd},
	booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
	{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
	pages     = {887--898},
	year      = {2012}}


@inproceedings{le2012faster,
	title={Faster algorithms for rectangular matrix multiplication},
	author={Le Gall, Fran{\c{c}}ois},
	booktitle={2012 IEEE 53rd annual symposium on foundations of computer science},
	pages={514--523},
	year={2012},
	organization={IEEE}
}

@article{lotti1983asymptotic,
	title={On the asymptotic complexity of rectangular matrix multiplication},
	author={Lotti, Grazia and Romani, Francesco},
	journal={Theoretical Computer Science},
	volume={23},
	number={2},
	pages={171--185},
	year={1983},
	publisher={Elsevier}
}

@inproceedings{mih10,
	title={Cell-probe lower bounds for succinct partial sums},
	author={P{\u{a}}tra{\c{s}}cu, Mihai and Viola, Emanuele},
	booktitle={Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms},
	pages={117--122},
	year={2010},
	organization={Society for Industrial and Applied Mathematics}
}

@inproceedings{chan17,
	title={Dynamic Orthogonal Range Searching on the RAM, Revisited},
	author={Chan, Timothy M and Tsakalidis, Konstantinos},
	booktitle={LIPIcs-Leibniz International Proceedings in Informatics},
	volume={77},
	year={2017},
	organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}

@inproceedings{gag17,
	Author = {Gagie, Travis and He, Meng and Navarro, Gonzalo},
	Booktitle = {Data Compression Conference (DCC), 2017},
	Organization = {IEEE},
	Pages = {260--269},
	Title = {Compressed Dynamic Range Majority Data Structures},
	Year = {2017}
}

@inproceedings{elm11,
	Author = {Elmasry, Amr and He, Meng and Munro, J Ian and Nicholson, Patrick K},
	Booktitle = {International Symposium on Algorithms and Computation},
	Organization = {Springer},
	Pages = {150--159},
	Title = {Dynamic range majority data structures},
	Year = {2011}
}

@inproceedings{Williams20,
	Author = {Virginia Vassilevska Williams and Yinzhan Xu},
	Booktitle = {Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms},
	Date-Added = {2020-02-05 14:15:25 -0500},
	Date-Modified = {2020-02-05 14:18:48 -0500},
	Title = {Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications},
	Year = {2020}
}

@inproceedings{Fischer71,
	Author = {Michael J Fischer and Albert R Meyer},
	Booktitle = {n 12th Annual Symposium on Switching and Automata Theory},
	Date-Added = {2020-02-05 15:38:19 -0500},
	Date-Modified = {2020-02-05 15:41:52 -0500},
	Pages = {129-131},
	Publisher = {IEEE},
	Title = {Boolean matrix multiplication and transitive closure},
	Year = {1971}
}

@article{Bringmann17,
	author = {Bringmann, Karl and Grandoni, Fabrizio and Saha, Barna and Williams, Virginia},
	year = {2017},
	month = {07},
	pages = {},
	title = {Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product},
	volume = {48},
	journal = {SIAM Journal on Computing},
	doi = {10.1137/17M112720X}
}

@article{Seidel95,
	Author = {Raimund Seidel},
	Date-Added = {2020-02-05 18:12:21 -0500},
	Date-Modified = {2020-02-05 18:13:43 -0500},
	Journal = {J. Comput. Syst. Sci.},
	Number = {3},
	Pages = {400-403},
	Title = {On the all-pairs-shortest-path problem in unweighted undirected graphs},
	Volume = { 51},
	Year = {1995}
}

@inproceedings{Shoshan99,
	Author = {Avi Shoshan and Uri Zwick},
	Booktitle = {40th Annual IEEE Symposium on Foundations of Computer Science},
	Date-Added = {2020-02-05 18:14:49 -0500},
	Date-Modified = {2020-02-05 18:16:12 -0500},
	Pages = {605-615},
	Title = {All pairs shortest paths in undirected graphs with integer weights},
	Year = {1999}
}

@article{Zwick02,
	Author = {Uri Zwick},
	Date-Added = {2020-02-05 18:17:19 -0500},
	Date-Modified = {2020-02-05 18:18:02 -0500},
	Journal = {J. ACM},
	Number = {3},
	Pages = {289--317},
	Title = {All pairs shortest paths using bridging sets and rectangular matrix multiplication},
	Volume = {49},
	Year = {2002}
}

@article{Chan10,
	Author = {Timothy M. Chan},
	Date-Added = {2020-02-05 18:19:22 -0500},
	Date-Modified = {2020-02-05 18:20:19 -0500},
	Journal = {SIAM J. Comput.},
	Number = {5},
	Pages = {2075--2089},
	Title = {More algorithms for all-pairs shortest paths in weighted graphs},
	Volume = {39},
	Year = {2010}
}

@inproceedings{Yuster09,
	Author = {Raphael Yuster},
	Booktitle = {20th Annual ACM-SIAM Symposium on Discrete Algorithms},
	Date-Added = {2020-02-05 18:21:11 -0500},
	Date-Modified = {2020-02-05 18:22:12 -0500},
	Pages = {950--957},
	Title = {Efficient algorithms on sets of permutations, dominance, and real-weighted APSP},
	Year = {2009}
}

@inproceedings{Henzinger15,
	author = {Henzinger, Monika and Krinninger, Sebastian and Nanongkai, Danupon and Saranurak, Thatchaphol},
	title = {Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture},
	year = {2015},
	booktitle = {Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing},
	pages = {21–30}
}

@book{overmars1983design,
	title={The design of dynamic data structures},
	author={Overmars, Mark H},
	volume={156},
	year={1983},
	publisher={Springer Science \& Business Media}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: Succinct Approximate Range Mode
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@article{WX20,
	Author = {Virginia Vassilevska Williams and Yinzhan Xu},
	Date-Added = {2019-09-09 17:30:30 -0400},
	Date-Modified = {2019-09-09 17:31:15 -0400},
	Title = {Truly Subcubic Min-Plus Product for Less Structured Matrices, with Applications},
	Year = {2020}}

@inproceedings{YusterZ05,
	Author = {Raphael Yuster and Uri Zwick},
	Booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS} 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
	Pages = {389--396},
	Title = {Answering distance queries in directed graphs using fast matrix multiplication},
	Year = {2005}}

@article{Zwick00,
	Author = {Uri Zwick},
	Journal = {CoRR},
	Title = {All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication},
	Volume = {cs.DS/0008011},
	Year = {2000}}

@inproceedings{Patrascu08,
	Author = {M. {Patrascu}},
	Booktitle = {2008 49th Annual IEEE Symposium on Foundations of Computer Science},
	Pages = {305-313},
	Title = {Succincter},
	Year = {2008}}

@inproceedings{ElZein17,
	Author = {Hicham El-Zein and J. Ian Munro and Yakov Nekrich},
	Booktitle = {ISAAC},
	Title = {Succinct Color Searching in One Dimension},
	Year = {2017}}

@inproceedings{Fredman90,
	Author = {Fredman, M. L. and Willard, D. E.},
	Booktitle = {Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing},
	Isbn = {0-89791-361-2},
	Location = {Baltimore, Maryland, USA},
	Numpages = {7},
	Pages = {1--7},
	Series = {STOC '90},
	Title = {BLASTING Through the Information Theoretic Barrier with FUSION TREES},
	Year = {1990}}

@inproceedings{jl2011,
	Author = {Allan Gr{\o}nlund J{\o}rgensen and Kasper Green Larsen},
	Booktitle = {Proceedings of the 22nd Annual {ACM-SIAM} Symposium on Discrete Algorithms},
	Pages = {805--813},
	Title = {Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures},
	Year = {2011}}

@inproceedings{bkpt2005,
	Author = {Prosenjit Bose and Evangelos Kranakis and Pat Morin and Yihui Tang},
	Booktitle = {Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science},
	Pages = {377--388},
	Title = {Approximate Range Mode and Range Median Queries},
	Year = {2005}}

@article{ginrr2017,
	Author = {Roberto Grossi and John Iacono and Gonzalo Navarro and Rajeev Raman and S. Srinivasa Rao},
	Journal = {{ACM} Transactions on Algorithms},
	Number = {2},
	Pages = {28:1--28:31},
	Title = {Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-\emph{k} Queries},
	Volume = {13},
	Year = {2017}}

@article{fh2011,
	Author = {Johannes Fischer and Volker Heun},
	Journal = {{SIAM} Journal on Computing},
	Number = {2},
	Pages = {465--492},
	Title = {Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays},
	Volume = {40},
	Year = {2011}}

@inproceedings{W12,
	Author = {Virginia Vassilevska Williams},
	Booktitle = {Proceedings of the fourty-fourth annual symposium on theory of computing},
	Date-Added = {2018-02-17 06:38:15 +0000},
	Date-Modified = {2018-02-17 06:39:09 +0000},
	Title = {Multiplying matrices faster than coppersmith-winograd},
	Year = {2012}}

@article{cw2016,
	Author = {Timothy M. Chan and Bryan T. Wilkinson},
	Journal = {{ACM} Trans. Algorithms},
	Number = {4},
	Pages = {45:1--45:15},
	Title = {Adaptive and Approximate Orthogonal Range Counting},
	Volume = {12},
	Year = {2016}}

@article{pg2009,
	Author = {Holger Petersen and Szymon Grabowski},
	Journal = {Information Processing Letters},
	Number = {4},
	Pages = {225--228},
	Title = {Range mode and range median queries in constant time and sub-quadratic space},
	Volume = {109},
	Year = {2009}}

@inproceedings{p2008,
	Author = {Holger Petersen},
	Booktitle = {Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science},
	Pages = {418--423},
	Title = {Improved Bounds for Range Mode and Range Median Queries},
	Year = {2008}}

@inproceedings{gpt2009,
	Author = {Travis Gagie and Simon J. Puglisi and Andrew Turpin},
	Booktitle = {Proceedings of the 16th International Symposium on String Processing and Information Retrieval},
	Pages = {1--6},
	Title = {Range Quantile Queries: Another Virtue of Wavelet Trees},
	Year = {2009}}

@inproceedings{bj2009,
	Author = {Gerth St{\o}lting Brodal and Allan Gr{\o}nlund J{\o}rgensen},
	Booktitle = {Proceedings of the 20th International Symposium on Algorithms and Computation},
	Pages = {822--831},
	Title = {Data Structures for Range Median Queries},
	Year = {2009}}

@inproceedings{gn2015,
	Author = {Pawel Gawrychowski and Patrick K. Nicholson},
	Booktitle = {Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming},
	Pages = {593--604},
	Title = {Optimal Encodings for Range Top- k k , Selection, and Min-Max},
	Year = {2015}}

@inproceedings{Patrascu08a,
	Author = {Mihai Patrascu},
	Booktitle = {Proceedings of the 49th Annual {IEEE} Symposium on Foundations of Computer Science},
	Pages = {434--443},
	Title = {(Data) {STRUCTURES}},
	Year = {2008}}

@inproceedings{Dietz89a,
	Author = {Paul F. Dietz},
	Booktitle = {Proceedings of Workshop on Algorithms and Data Structures ({WADS})},
	Doi = {10.1007/3-540-51542-9\_8},
	Pages = {67--74},
	Title = {Fully Persistent Arrays (Extended Array)},
	Year = {1989},
	Bdsk-Url-1 = {https://doi.org/10.1007/3-540-51542-9%5C_8}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: Offline Dynamic Higher Connectivity
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%


@mastersthesis{MT12,
	Author = {Sergey Kopeliovich},
	School = {Saint Petersburg State University},
	Title = {Offline solution of connectivity and $2$-edge-connectivity problems for fully dynamic graphs},
	Year = {2012}}

@inproceedings{HRT18,
	Author = {Jacob Holm and Eva Rotenberg and Mikkel Thorup},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2018-04-18 08:44:54 +0000},
	Date-Modified = {2018-04-18 08:53:10 +0000},
	Title = {Dynamic bridge-finding in $\tilde{O}(\log^2 n)$ amortized time},
	Year = {2018}}

@phdthesis{Weiskircher02,
	Author = {Rene Weiskircher},
	Date-Added = {2017-07-05 22:37:18 +0000},
	Date-Modified = {2017-07-05 22:39:10 +0000},
	School = {Universit{\"a}t des Saarlandes},
	Title = {New Applications of SPQR-Trees in Graph Drawing},
	Year = {2002}}

@article{DurfeePPR17:arxiv,
	Author = {David Durfee and John Peebles and Richard Peng and Anup B. Rao},
	Journal = {CoRR},
	Title = {Determinant-Preserving Sparsification of {SDDM} Matrices with Applications to Counting and Sampling Spanning Trees},
	Url = {http://arxiv.org/abs/1705.00985},
	Volume = {abs/1705.00985},
	Year = {2017},
	Bdsk-Url-1 = {http://arxiv.org/abs/1705.00985}}

@article{CohenMTV17:arxiv,
	Author = {Michael B. Cohen and Aleksander Madry and Dimitris Tsipras and Adrian Vladu},
	Journal = {CoRR},
	Title = {Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods},
	Url = {http://arxiv.org/abs/1704.02310},
	Volume = {abs/1704.02310},
	Year = {2017},
	Bdsk-Url-1 = {http://arxiv.org/abs/1704.02310}}

@article{KrauthgamerR17,
	Author = {Robert Krauthgamer and Inbal Rika},
	Journal = {CoRR},
	Title = {Refined Vertex Sparsifiers of Planar Graphs},
	Url = {http://arxiv.org/abs/1702.05951},
	Volume = {abs/1702.05951},
	Year = {2017},
	Bdsk-Url-1 = {http://arxiv.org/abs/1702.05951}}

@article{EnglertGKRTT14,
	Author = {Matthias Englert and Anupam Gupta and Robert Krauthgamer and Harald Racke and Inbal Talgam{-}Cohen and Kunal Talwar},
	Journal = {{SIAM} J. Comput.},
	Number = {4},
	Pages = {1239--1262},
	Title = {Vertex Sparsifiers: New Results from Old Techniques},
	Url = {https://arxiv.org/abs/1006.4586},
	Volume = {43},
	Year = {2014},
	Bdsk-Url-1 = {https://arxiv.org/abs/1006.4586}}

@inproceedings{NanongkaiS17,
	Author = {Danupon Nanongkai and Thatchaphol Saranurak},
	Booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2017, Montreal, QC, Canada, June 19-23, 2017},
	Pages = {1122--1129},
	Title = {Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and ${O}(n^{1/2 - \epsilon})$-time},
	Url = {https://arxiv.org/abs/1611.03745},
	Year = {2017},
	Bdsk-Url-1 = {https://arxiv.org/abs/1611.03745}}

@inproceedings{Wulff-Nilsen17,
	Author = {Christian Wulff{-}Nilsen},
	Booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC}},
	Pages = {1130--1143},
	Title = {Fully-dynamic minimum spanning forest with improved worst-case update time},
	Year = {2017}}

@inproceedings{KargerP09,
	Author = {Karger, David R and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Organization = {Society for Industrial and Applied Mathematics},
	Pages = {246--255},
	Title = {A near-linear time algorithm for constructing a cactus representation of minimum cuts},
	Year = {2009}}

@inproceedings{BhalgatHKP08,
	Author = {Bhalgat, Anand and Hariharan, Ramesh and Kavitha, Telikepalli and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms},
	Organization = {Society for Industrial and Applied Mathematics},
	Pages = {455--464},
	Title = {Fast edge splitting and Edmonds' arborescence construction for unweighted graphs},
	Url = {https://users.cs.duke.edu/\textasciitilde debmalya/papers/soda08-splitting.pdf},
	Year = {2008},
	Bdsk-Url-1 = {https://users.cs.duke.edu/%5Ctextasciitilde%20debmalya/papers/soda08-splitting.pdf}}

@inproceedings{AbrahamDKKP16,
	Author = {I. {Abraham} and D. {Durfee} and I. {Koutis} and S. {Krinninger} and R. {Peng}},
	Booktitle = {2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)},
	Issn = {0272-5428},
	Month = {Oct},
	Pages = {335-344},
	Title = {On Fully Dynamic Graph Sparsifiers},
	Year = {2016}}

@inproceedings{DurfeeKPRS17,
	Author = {David Durfee and Rasmus Kyng and John Peebles and Anup B. Rao and Sushant Sachdeva},
	Booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing},
	Pages = {730--742},
	Title = {Sampling random spanning trees faster than matrix multiplication},
	Year = {2017}}

@inproceedings{GoranciHT16,
	Author = {Goranci, Gramoz and Henzinger, Monika and Thorup, Mikkel},
	Booktitle = {LIPIcs-Leibniz International Proceedings in Informatics},
	Organization = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik},
	Title = {Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time},
	Url = {https://arxiv.org/abs/1611.06500},
	Volume = {57},
	Year = {2016},
	Bdsk-Url-1 = {https://arxiv.org/abs/1611.06500}}

@inproceedings{AbboudWY15,
	Author = {Amir Abboud and Virginia Vassilevska Williams and Huacheng Yu},
	Booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory of Computing, {STOC} 2015},
	Pages = {41--50},
	Title = {Matching Triangles and Basing Hardness on an Extremely Popular Conjecture},
	Year = {2015}}

@inproceedings{FungHHP11,
	Acmid = {1993647},
	Address = {New York, NY, USA},
	Author = {Fung, Wai Shing and Hariharan, Ramesh and Harvey, Nicholas J.A. and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing},
	Isbn = {978-1-4503-0691-1},
	Keywords = {edge connectivity, graph sparsification, sampling},
	Location = {San Jose, Caliberfornia, USA},
	Numpages = {10},
	Pages = {71--80},
	Publisher = {ACM},
	Series = {STOC '11},
	Title = {A General Framework for Graph Sparsification},
	Url = {http://arxiv.org/abs/1004.4080},
	Year = {2011},
	Bdsk-Url-1 = {http://arxiv.org/abs/1004.4080}}

@article{HariharanP10,
	Author = {Ramesh Hariharan and Debmalya Panigrahi},
	Bibsource = {dblp computer science bibliography, http://dblp.org},
	Biburl = {http://dblp.uni-trier.de/rec/bib/journals/corr/abs-1005-0670},
	Journal = {CoRR},
	Timestamp = {Mon, 05 Dec 2011 18:04:58 +0100},
	Title = {A Linear-time Algorithm for Sparsification of Unweighted Graphs},
	Url = {http://arxiv.org/abs/1005.0670},
	Volume = {abs/1005.0670},
	Year = {2010},
	Bdsk-Url-1 = {http://arxiv.org/abs/1005.0670}}

@inproceedings{BenczurK96,
	Acmid = {237827},
	Address = {New York, NY, USA},
	Author = {Bencz\'{u}r, Andr\'{a}s A. and Karger, David R.},
	Booktitle = {Proceedings of the twenty-eighth annual ACM symposium on Theory of computing},
	Isbn = {0-89791-785-5},
	Location = {Philadelphia, Pennsylvania, USA},
	Numpages = {9},
	Pages = {47--55},
	Publisher = {ACM},
	Series = {STOC '96},
	Title = {Approximating s-t minimum cuts in $\tilde{O}(n^2)$ time},
	Year = {1996}}

@inproceedings{HariharanKP07,
	Author = {Hariharan, Ramesh and Kavitha, Telikepalli and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
	Organization = {Society for Industrial and Applied Mathematics},
	Pages = {127--136},
	Title = {Efficient algorithms for computing all low st edge connectivities and related problems},
	Year = {2007}}

@inproceedings{GalilI91,
	Author = {Galil, Zvi and Italiano, Giuseppe F},
	Booktitle = {Proceedings of the twenty-third annual ACM symposium on Theory of computing},
	Organization = {ACM},
	Pages = {317--327},
	Title = {Fully dynamic algorithms for edge connectivity problems},
	Year = {1991}}

@article{Tsin09,
	Author = {Tsin, Yung H},
	Journal = {Journal of Discrete Algorithms},
	Number = {1},
	Pages = {130--146},
	Publisher = {Elsevier},
	Title = {Yet another optimal algorithm for 3-edge-connectivity},
	Volume = {7},
	Year = {2009}}

@article{DinitzKL76,
	Author = {Dinitz, Efim A and Karzanov, Alexander V and Lomonosov, Michael V},
	Title = {On the structure of the system of minimum edge cuts in a graph},
	Year = {1976}}

@inproceedings{DinitzV94,
	Author = {Dinitz, Yefim and Vainshtein, Alek},
	Booktitle = {Proceedings of the twenty-sixth annual ACM symposium on Theory of computing},
	Organization = {ACM},
	Pages = {716--725},
	Title = {The connectivity carcass of a vertex subset in a graph and its incremental maintenance},
	Year = {1994}}

@inproceedings{DinitzV95,
	Author = {Dinitz, Ye. and Vainshtein, A.},
	Booktitle = {Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Isbn = {0-89871-349-8},
	Location = {San Francisco, California, USA},
	Numpages = {10},
	Pages = {302--311},
	Series = {SODA '95},
	Title = {Locally Orientable Graphs, Cell Structures, and a New Algorithm for the Incremental Maintenance of Connectivity Carcasses},
	Year = {1995}}

@article{FleinerF09,
	Author = {Fleiner, Tam{\'a}s and Frank, Andr{\'a}s},
	Title = {A quick proof for the cactus representation of mincuts},
	Url = {http://www.cs.elte.hu/\textasciitilde frank/cikkek/FrankR3.pdf},
	Year = {2009},
	Bdsk-Url-1 = {http://www.cs.elte.hu/%5Ctextasciitilde%20frank/cikkek/FrankR3.pdf}}

@inproceedings{Frederickson1983,
	Acmid = {808754},
	Address = {New York, NY, USA},
	Author = {Frederickson, Greg N.},
	Booktitle = {Proceedings of the fifteenth annual ACM symposium on Theory of computing},
	Isbn = {0-89791-099-0},
	Numpages = {6},
	Pages = {252--257},
	Publisher = {ACM},
	Series = {STOC '83},
	Title = {Data structures for on-line updating of minimum spanning trees},
	Year = {1983}}

@inproceedings{Thorup00,
	Acmid = {335345},
	Address = {New York, NY, USA},
	Author = {Thorup, Mikkel},
	Booktitle = {Proceedings of the thirty-second annual ACM symposium on Theory of computing},
	Isbn = {1-58113-184-4},
	Location = {Portland, Oregon, USA},
	Numpages = {8},
	Pages = {343--350},
	Publisher = {ACM},
	Series = {STOC '00},
	Title = {Near-optimal fully-dynamic graph connectivity},
	Year = {2000}}

@article{HenzingerKing99,
	Author = {Monika Rauch Henzinger and Valerie King},
	Journal = {JOURNAL OF THE ACM},
	Pages = {516},
	Title = {Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation},
	Volume = {46},
	Year = {1999}}

@misc{IyerKRT00,
	Author = {Raj D. Iyer and David Karger and Hariharan S. Rahul and Mikkel Thorup},
	Title = {An Experimental Study of Poly-Logarithmic Fully-Dynamic Connectivity Algorithms},
	Year = {2000}}

@inproceedings{HolmLT98,
	Acmid = {276715},
	Address = {New York, NY, USA},
	Author = {Holm, Jacob and de Lichtenberg, Kristian and Thorup, Mikkel},
	Booktitle = {Proceedings of the thirtieth annual ACM symposium on Theory of computing},
	Isbn = {0-89791-962-9},
	Location = {Dallas, Texas, USA},
	Numpages = {11},
	Pages = {79--89},
	Publisher = {ACM},
	Series = {STOC '98},
	Title = {Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity},
	Year = {1998}}

@article{AlstrupHLT2005,
	Acmid = {1103966},
	Address = {New York, NY, USA},
	Author = {Alstrup, Stephen and Holm, Jacob and Lichtenberg, Kristian De and Thorup, Mikkel},
	Issn = {1549-6325},
	Issue_Date = {October 2005},
	Journal = {ACM Trans. Algorithms},
	Keywords = {Fully dynamic forest},
	Month = oct,
	Number = {2},
	Numpages = {22},
	Pages = {243--264},
	Publisher = {ACM},
	Title = {Maintaining information in fully dynamic trees with top trees},
	Volume = {1},
	Year = {2005}}

@article{HopcroftT73,
	Author = {John E. Hopcroft and Robert Endre Tarjan},
	Journal = {{SIAM} J. Comput.},
	Number = {3},
	Pages = {135--158},
	Title = {Dividing a Graph into Triconnected Components},
	Volume = {2},
	Year = {1973}}

@inproceedings{DiBattistaT89,
	Acmid = {1398728},
	Address = {Washington, DC, USA},
	Author = {Di Battista, G. and Tamassia, R.},
	Booktitle = {Proceedings of the 30th Annual Symposium on Foundations of Computer Science},
	Isbn = {0-8186-1982-1},
	Keywords = {edge insertions, incremental planarity testing, planar graph, supports tests, insertion, vertices, edges, queries, vertex insertions},
	Numpages = {6},
	Pages = {436--441},
	Publisher = {IEEE Computer Society},
	Series = {SFCS '89},
	Title = {Incremental planarity testing},
	Year = {1989}}

@article{GomoryH61,
	Author = {Gomory, R. E. and Hu, T. C.},
	Copyright = {Copyright {\copyright} 1961 Society for Industrial and Applied Mathematics},
	Issn = {03684245},
	Journal = {Journal of the Society for Industrial and Applied Mathematics},
	Language = {English},
	Number = {4},
	Pages = {pp. 551-570},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {Multi-Terminal Network Flows},
	Url = {http://www.jstor.org/stable/2098881},
	Volume = {9},
	Year = {1961},
	Bdsk-Url-1 = {http://www.jstor.org/stable/2098881}}

@article{Eppstein94,
	Acmid = {185278},
	Address = {Duluth, MN, USA},
	Author = {Eppstein, David},
	Issn = {0196-6774},
	Issue_Date = {Sept. 1994},
	Journal = {J. Algorithms},
	Month = sep,
	Number = {2},
	Numpages = {14},
	Pages = {237--250},
	Publisher = {Academic Press, Inc.},
	Title = {Offline algorithms for dynamic minimum spanning tree problems},
	Volume = {17},
	Year = {1994}}

@inproceedings{KaczmarzL15,
	Author = {Karczmarz, Adam and {\L}\k{a}cki, Jakub},
	Booktitle = {Algorithms and Data Structures: 14th International Symposium, WADS 2015},
	Editor = {Dehne, Frank and Sack, Jorg-Rudiger and Stege, Ulrike},
	Pages = {458--469},
	Title = {Fast and Simple Connectivity in Graph Timelines},
	Year = {2015}}

@article{LackiS13,
	Author = {Jakub {\L}\k{a}cki and Piotr Sankowski},
	Journal = {ITCS},
	Title = {Reachability in Graph Timelines},
	Year = {2013}}

@inproceedings{DemaineP04,
	Acmid = {1007435},
	Address = {New York, NY, USA},
	Author = {Patracscu, Mihai and Demaine, Erik D.},
	Booktitle = {Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
	Isbn = {1-58113-852-0},
	Keywords = {cell-probe complexity, dynamic connectivity, dynamic graph problems, lower bounds for data structures, partial sums problem},
	Location = {Chicago, IL, USA},
	Numpages = {8},
	Pages = {546--553},
	Publisher = {ACM},
	Series = {STOC '04},
	Title = {Lower bounds for dynamic connectivity},
	Year = {2004}}

@article{SleatorT85,
	Acmid = {2793},
	Address = {New York, NY, USA},
	Author = {Sleator, Daniel D. and Tarjan, Robert E.},
	Issn = {0001-0782},
	Issue_Date = {Feb. 1985},
	Journal = {Commun. ACM},
	Month = feb,
	Number = {2},
	Numpages = {7},
	Pages = {202--208},
	Publisher = {ACM},
	Title = {Amortized efficiency of list update and paging rules},
	Volume = {28},
	Year = {1985}}

@inproceedings{Fox11,
	Acmid = {2033225},
	Address = {Berlin, Heidelberg},
	Author = {Fox, Kyle},
	Booktitle = {Proceedings of the 12th international conference on Algorithms and data structures},
	Isbn = {978-3-642-22299-3},
	Location = {New York, NY},
	Numpages = {12},
	Pages = {411--422},
	Publisher = {Springer-Verlag},
	Series = {WADS'11},
	Title = {Upper bounds for maximally greedy binary search trees},
	Url = {http://dl.acm.org/citation.cfm?id=2033190.2033225},
	Year = {2011},
	Bdsk-Url-1 = {http://dl.acm.org/citation.cfm?id=2033190.2033225}}

@inproceedings{CharikarLSM10,
	Acmid = {1918391},
	Address = {Washington, DC, USA},
	Author = {Charikar, Moses and Leighton, Tom and Li, Shi and Moitra, Ankur},
	Booktitle = {Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science},
	Isbn = {978-0-7695-4244-7},
	Keywords = {vertex sparsifier, approximation algorithms},
	Numpages = {10},
	Pages = {265--274},
	Publisher = {IEEE Computer Society},
	Series = {FOCS '10},
	Title = {Vertex Sparsifiers and Abstract Rounding Algorithms},
	Year = {2010}}

@inproceedings{DiBattistaT90,
	Acmid = {92364},
	Address = {New York, NY, USA},
	Author = {Di Battista, Giuseppe and Tamassia, Roberto},
	Booktitle = {Proceedings of the seventeenth international colloquium on Automata, languages and programming},
	Isbn = {0-387-52826-1},
	Numpages = {14},
	Pages = {598--611},
	Title = {On-line graph algorithms with SPQR-trees},
	Year = {1990},
	Bdsk-Url-1 = {http://dl.acm.org/citation.cfm?id=90397.92364}}

@article{BienstockM88,
	Acmid = {45467},
	Address = {Philadelphia, PA, USA},
	Author = {Bienstock, Daniel and Monma, Clyde L.},
	Issn = {0097-5397},
	Issue_Date = {Feb. 1988},
	Journal = {SIAM J. Comput.},
	Month = feb,
	Number = {1},
	Numpages = {24},
	Pages = {53--76},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {On the complexity of covering vertices by faces in a planar graph},
	Volume = {17},
	Year = {1988}}

@techreport{SaxeB79,
	Author = {Saxe, James B. and Bentley, Jon Louis.},
	Institution = {CMU},
	Number = {2420},
	Title = {Transforming static data structures to dynamic structures},
	Url = {http://repository.cmu.edu/compsci/2420},
	Year = {1979},
	Bdsk-Url-1 = {http://repository.cmu.edu/compsci/2420}}

@inproceedings{MillerR87,
	Author = {Gary L. Miller and Vijaya Ramachandran},
	Booktitle = {Combinatorica},
	Pages = {254--263},
	Title = {A new graph triconnectivity algorithm and its parallelization},
	Year = {1987}}

@inproceedings{EdwardsV12,
	Acmid = {2312042},
	Address = {New York, NY, USA},
	Author = {Edwards, James Alexander and Vishkin, Uzi},
	Booktitle = {Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures},
	Isbn = {978-1-4503-1213-4},
	Keywords = {PRAM, graph algorithm, many-core, triconnected components},
	Location = {Pittsburgh, Pennsylvania, USA},
	Numpages = {3},
	Pages = {190--192},
	Publisher = {ACM},
	Series = {SPAA '12},
	Title = {Brief announcement: speedups for parallel graph triconnectivity},
	Year = {2012}}

@article{TarjanV85,
	Author = {Robert Endre Tarjan and Uzi Vishkin},
	Citedby = {0},
	Cites = {0},
	Journal = {SIAM J. Comput.},
	Number = {4},
	Pages = {862-874},
	Researchr = {http://researchr.org/publication/TarjanV85},
	Title = {An Efficient Parallel Biconnectivity Algorithm},
	Volume = {14},
	Year = {1985}}

@article{MillerR91,
	Author = {Gary L. Miller and John H. Reif},
	Journal = {SIAM JOURNAL ON COMPUTING},
	Number = {6},
	Pages = {1128--1147},
	Title = {Parallel Tree Contraction Part 2: Further Applications},
	Volume = {20},
	Year = {1991}}

@article{WestbrookT92,
	Author = {Westbrook, Jeffery and Tarjan, RobertE.},
	Issn = {0178-4617},
	Issue = {1-6},
	Journal = {Algorithmica},
	Keywords = {On-line algorithms; Graph algorithms; Graph connectivity; Dynamic trees; Data structures},
	Language = {English},
	Pages = {433-464},
	Publisher = {Springer-Verlag},
	Title = {Maintaining bridge-connected and biconnected components on-line},
	Volume = {7},
	Year = {1992}}

@inproceedings{KarczmarzL15,
	Author = {Adam Karczmarz and Jakub Lacki},
	Booktitle = {{WADS}},
	Pages = {458--469},
	Publisher = {Springer},
	Series = {Lecture Notes in Computer Science},
	Title = {Fast and Simple Connectivity in Graph Timelines},
	Volume = {9214},
	Year = {2015}}

@inproceedings{GoranciHP18:arxiv,
	Author = {Gramoz Goranci and Monika Henzinger and Pan Peng},
	Booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
	Pages = {40:1--40:15},
	Title = {Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs},
	Volume = {112},
	Year = {2018}}

@inproceedings{GoranciHP17,
	Author = {Gramoz Goranci and Monika Henzinger and Pan Peng},
	Booktitle = {European Symposium on Algorithms (ESA)},
	Pages = {45:1--45:14},
	Title = {The Power of Vertex Sparsifiers in Dynamic Graph Algorithms},
	Year = {2017}}

@article{LiPYZ18:arxiv,
	Author = {Huan Li and Stacy Patterson and Yuhao Yi and Zhongzhi Zhang},
	Journal = {CoRR},
	Title = {Maximizing the Number of Spanning Trees in a Connected Graph},
	Url = {https://arxiv.org/abs/1804.02785},
	Volume = {abs/1804.02785},
	Year = {2018},
	Bdsk-Url-1 = {https://arxiv.org/abs/1804.02785}}

@inproceedings{LiZ18,
	Author = {Li, Huan and Zhang, Zhongzhi},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Pages = {2377--2396},
	Title = {Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms},
	Year = {2018}}

@article{Sleator83,
	Abstract = {A data structure is proposed to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. Each operation requires O(log n) time. Using this data structure, new fast algorithms are obtained for the following problems: 1.(1) Computing nearest common ancestors.2.(2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows.3.(3) Computing certain kinds of constrained minimum spanning trees.4.(4) Implementing the network simplex algorithm for minimum-cost flows. The most significant application is (2); an O(mn log n)-time algorithm is obtained to find a maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest algorithm previously known for sparse graphs.},
	Author = {Daniel D. Sleator and Robert Endre Tarjan},
	Issn = {0022-0000},
	Journal = {Journal of Computer and System Sciences},
	Number = {3},
	Pages = {362 - 391},
	Title = {A data structure for dynamic trees},
	Url = {http://www.sciencedirect.com/science/article/pii/0022000083900065},
	Volume = {26},
	Year = {1983},
	Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/pii/0022000083900065}}

@article{Eppstein97,
	Acmid = {265914},
	Address = {New York, NY, USA},
	Author = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Nissenzweig, Amnon},
	Issn = {0004-5411},
	Issue_Date = {Sept. 1997},
	Journal = {J. ACM},
	Keywords = {dynamic graph algorithms, edge and vertex connectivity, minimum spanning trees},
	Month = sep,
	Number = {5},
	Numpages = {28},
	Pages = {669--696},
	Publisher = {ACM},
	Title = {Sparsification--A Technique for Speeding Up Dynamic Graph Algorithms},
	Volume = {44},
	Year = {1997}}

@inproceedings{Huang17,
	Acmid = {3039718},
	Author = {Huang, Shang-En and Huang, Dawei and Kopelowitz, Tsvi and Pettie, Seth},
	Booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Location = {Barcelona, Spain},
	Numpages = {11},
	Pages = {510--520},
	Title = {Fully Dynamic Connectivity in {$O(\log n(\log \log n)^2)$} Amortized Expected Time},
	Year = {2017}}

@inproceedings{Holm15,
	Abstract = {We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in O(log4				n/loglogn) expected amortized time per operation, improving the O(log4				n) amortized bound of Holm et al. (STOC '98, JACM '01). We also provide a deterministic data structure with amortized update time O(log4				n logloglogn/loglogn). We assume the Word-RAM model with standard instructions.},
	Address = {Berlin, Heidelberg},
	Author = {Holm, Jacob and Rotenberg, Eva and Wulff-Nilsen, Christian},
	Booktitle = {Algorithms - ESA 2015},
	Editor = {Bansal, Nikhil and Finocchi, Irene},
	Isbn = {978-3-662-48350-3},
	Pages = {742--753},
	Publisher = {Springer Berlin Heidelberg},
	Title = {Faster Fully-Dynamic Minimum Spanning Forest},
	Year = {2015}}

@inproceedings{Durfee19,
	Author = {Durfee, David and Gao, Yu and Goranci, Gramoz and Peng, Richard},
	Booktitle = {Proceedings of the thirtieth annual ACM symposium on Theory of computing},
	Publisher = {ACM},
	Series = {STOC '19},
	Title = {Fully Dynamic Spectral Vertex Sparsifiers and Applications},
	Year = {2019}}

@inproceedings{Eppstein06,
	Author = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Spencer, Thomas H.},
	Booktitle = {Siam Journal on Computing},
	Date-Added = {2019-02-20 22:03:46 +0000},
	Date-Modified = {2019-02-20 22:05:33 +0000},
	Title = {Separator-Based Sparsification {II}: edge and Vertex Connectivity},
	Year = {2006}}

@article{Goranci18,
	Author = {Gramoz Goranci and Monika Henzinger and Thatchaphol Saranurak},
	Date-Added = {2019-02-20 22:09:35 +0000},
	Date-Modified = {2019-02-20 22:13:11 +0000},
	Journal = {CoRR},
	Title = {Fast Incremental Algorithms via Local Sparsifiers},
	Url = {https://drive.google.com/file/d/1SJrbzuz\_szMwsBfeBZfGUWkDEbZKAGD5/view},
	Year = {2018},
	Bdsk-Url-1 = {https://drive.google.com/file/d/1SJrbzuz%5C_szMwsBfeBZfGUWkDEbZKAGD5/view}}

@inproceedings{Kratsch12,
	Author = {Kratsch, Stefan and Wahlstrom, Magnus},
	Booktitle = {Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science},
	Isbn = {978-0-7695-4874-6},
	Numpages = {10},
	Pages = {450--459},
	Series = {FOCS '12},
	Title = {Representative Sets and Irrelevant Vertices: New Tools for Kernelization},
	Year = {2012}}

@inproceedings{Assadi2015DynamicSF,
	Author = {Sepehr Assadi and Sanjeev Khanna and Yang Li and Val Tannen},
	Booktitle = {FSTTCS},
	Title = {Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches},
	Year = {2015}}

@inproceedings{Fafianie16,
	Author = {Stefan Fafianie and Stefan Kratsch and Vuong Anh Quyen},
	Booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
	Pages = {33:1--33:13},
	Title = {Preprocessing Under Uncertainty},
	Volume = {47},
	Year = {2016}}

@inproceedings{Fafianie16b,
	Author = {Stefan Fafianie and Eva-Maria C. Hols and Stefan Kratsch and Vuong Anh Quyen},
	Booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
	Pages = {35:1--35:14},
	Title = {Preprocessing Under Uncertainty: Matroid Intersection},
	Volume = {58},
	Year = {2016}}

@article{PengSS,
	Archiveprefix = {arXiv},
	Author = {Richard Peng and Bryce Sandlund and Daniel Dominic Sleator},
	Bibsource = {dblp computer science bibliography, https://dblp.org},
	Biburl = {https://dblp.org/rec/bib/journals/corr/abs-1708-03812},
	Eprint = {1708.03812},
	Journal = {CoRR},
	Timestamp = {Mon, 13 Aug 2018 16:49:10 +0200},
	Title = {Offline Dynamic Higher Connectivity},
	Url = {http://arxiv.org/abs/1708.03812},
	Volume = {abs/1708.03812},
	Year = {2017},
	Bdsk-Url-1 = {http://arxiv.org/abs/1708.03812}}

@misc{Molina19,
	Author = {Molina, Antonio and Sandlund, Bryce},
	Date = {2018-11-28},
	Howpublished = {personal communication}}

@inproceedings{Abboud14,
	Acmid = {2707409},
	Author = {Abboud, Amir and Williams, Virginia Vassilevska},
	Booktitle = {Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science},
	Isbn = {978-1-4799-6517-5},
	Keywords = {dynamic algorithms, all pairs shortest paths, 3SUM, lower bounds},
	Numpages = {10},
	Pages = {434--443},
	Series = {FOCS '14},
	Title = {Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems},
	Year = {2014}}

@inproceedings{Abboud16,
	Author = {Abboud, Amir and Dahlgaard, Soren},
	Booktitle = {IEEE 57th Annual Symposium on Foundations of Computer Science},
	Month = {10},
	Pages = {477-486},
	Title = {Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms},
	Year = {2016}}

@inproceedings{Dahlgaard16,
	Author = {Dahlgaard, Soren},
	Booktitle = {43rd International Colloquium on Automata, Languages, and Programming},
	Date-Added = {2019-02-20 23:36:01 +0000},
	Date-Modified = {2019-02-21 00:02:41 +0000},
	Title = {On the hardness of partially dynamic graph problems and connections to diameter},
	Year = {2016}}

@article{Bringmann18,
	Author = {Karl Bringmann and Marvin Kunnemann and Andre Nusser},
	Journal = {CoRR},
	Title = {Frechet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability},
	Url = {https://arxiv.org/abs/1810.10982},
	Volume = {abs/1810.10982},
	Year = {2018},
	Bdsk-Url-1 = {https://arxiv.org/abs/1810.10982}}

@article{Moitra,
	author = {Moitra, A.},
	title = {Vertex Sparsification and Oblivious Reductions},
	journal = {SIAM Journal on Computing},
	volume = {42},
	number = {6},
	pages = {2400-2423},
	year = {2013},
	doi = {10.1137/100787337},
	URL = {https://doi.org/10.1137/100787337},
	eprint = {https://doi.org/10.1137/100787337}
}

@Article{DinitzW,
	author="Dinitz, Ye.
	and Westbrook, J.",
	title="Maintaining the Classes of 4-Edge-Connectivity in a Graph On-Line ",
	journal="Algorithmica",
	year="1998",
	month="Mar",
	day="01",
	volume="20",
	number="3",
	pages="242--276",
	issn="1432-0541",
	doi="10.1007/PL00009195",
	url="https://doi.org/10.1007/PL00009195"
}

@inproceedings{Gabow,
	author = {Gabow, Harold N.},
	title = {Algorithms for Graphic Polymatroids and Parametric s-Sets},
	booktitle = {Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms},
	series = {SODA '95},
	year = {1995},
	isbn = {0-89871-349-8},
	location = {San Francisco, California, USA},
	pages = {88--97},
	numpages = {10},
	url = {http://dl.acm.org/citation.cfm?id=313651.313667},
	acmid = {313667},
	publisher = {Society for Industrial and Applied Mathematics},
	address = {Philadelphia, PA, USA},
}

@book{CormenLRS,
	author = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
	title = {Introduction to Algorithms, Third Edition},
	year = {2009},
	isbn = {0262033844, 9780262033848},
	edition = {3rd},
	publisher = {The MIT Press},
}

@article{Tarjan,
	author = {Tarjan, R.},
	title = {Depth-First Search and Linear Graph Algorithms},
	journal = {SIAM Journal on Computing},
	volume = {1},
	number = {2},
	pages = {146-160},
	year = {1972},
	doi = {10.1137/0201010},
	URL = {https://doi.org/10.1137/0201010},
	eprint = {https://doi.org/10.1137/0201010}
}

@article{TarjanLCA,
	author = {Tarjan, Robert Endre},
	title = {Applications of Path Compression on Balanced Trees},
	journal = {J. ACM},
	issue_date = {Oct. 1979},
	volume = {26},
	number = {4},
	month = oct,
	year = {1979},
	issn = {0004-5411},
	pages = {690--715},
	numpages = {26},
	url = {http://doi.acm.org/10.1145/322154.322161},
	doi = {10.1145/322154.322161},
	acmid = {322161},
	publisher = {ACM},
	address = {New York, NY, USA},
}

@article{Gabow19,
	title = "A linear-time algorithm for a special case of disjoint set union",
	journal = "Journal of Computer and System Sciences",
	volume = "30",
	number = "2",
	pages = "209 - 221",
	year = "1985",
	issn = "0022-0000",
	doi = "https://doi.org/10.1016/0022-0000(85)90014-5",
	url = "http://www.sciencedirect.com/science/article/pii/0022000085900145",
	author = "Harold N. Gabow and Robert Endre Tarjan"
}

@article{Patrascu06,
	author = {Patrascu, Mihai and Demaine, Erik D.},
	title = {Logarithmic Lower Bounds in the Cell-Probe Model},
	journal = {SIAM J. Comput.},
	issue_date = {2006},
	volume = {35},
	number = {4},
	month = apr,
	year = {2006},
	issn = {0097-5397},
	pages = {932--963},
	numpages = {32},
	url = {http://dx.doi.org/10.1137/S0097539705447256},
	doi = {10.1137/S0097539705447256},
	acmid = {1117880},
	publisher = {Society for Industrial and Applied Mathematics},
	address = {Philadelphia, PA, USA},
	keywords = {cell-probe complexity, data structures, dynamic graph problems, lower bounds, partial-sums problem},
} 

@InProceedings{Ian,
	author="Munro, J. Ian",
	editor="Paterson, Mike S.",
	title="On the Competitiveness of Linear Search",
	booktitle="Algorithms - ESA 2000",
	year="2000",
	publisher="Springer Berlin Heidelberg",
	address="Berlin, Heidelberg",
	pages="338--345",
	abstract="We re-examine offline techniques for linear search. Under a reasonable model of computation, a method is given to perform offline linear search in amortized cost proportional to the entropy of the request sequence; and so, this cost is at most logarithmic. On the other hand, any online technique is subject to linear amortized cost for some sequences. It follows, then, that no online technique can have an amortized cost of that which one could obtain if given the request sequence in advance, i.e., there is no competitive linear search algorithm.",
	isbn="978-3-540-45253-9"
}

@article{Thorup07,
	author = {Thorup, Mikkel},
	title = {Fully-Dynamic Min-Cut},
	journal = {Combinatorica},
	issue_date = {February 2007},
	volume = {27},
	number = {1},
	month = feb,
	year = {2007},
	issn = {0209-9683},
	pages = {91--127},
	numpages = {37},
	url = {https://doi.org/10.1007/s00493-007-0045-2},
	doi = {10.1007/s00493-007-0045-2},
	acmid = {1229816},
	publisher = {Springer-Verlag},
	address = {Berlin, Heidelberg},
	keywords = {05C40, 05C85, 68R10, 68W05, 90B10, 90B25, 94C12, 94C15},
}

@InProceedings{DinitzNossenson00,
	author="Dinitz, Yefim
	and Nossenson, Ronit",
	title="Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph",
	booktitle="Algorithm Theory - SWAT 2000",
	year="2000",
	publisher="Springer Berlin Heidelberg",
	address="Berlin, Heidelberg",
	pages="272--285",
	abstract="Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them. The equivalence classes of this relation are called k-edge-connected classes, or k-classes for short. This paper shows how to check whether two vertices belong to the same 5-class of an arbitrary connected graph that is undergoing edge insertions. For this purpose we suggest (i) a full description of the 4-cuts of an arbitrary graph and (ii) a representation of the k-classes, 1 = k = 5, of size linear in n-the number of vertices of the graph; these representations can be constructed in a polynomial time. Using them, we suggest an algorithm for incremental maintenance of the 5-classes. The total time for a sequence of m Edge-Insert updates and q Same-5-Class? queries is O(q + m + n {\textperiodcentered} log2n); the worst-case time per query is O(1).",
	isbn="978-3-540-44985-0"
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Section: Minimum Cuts
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@article{Karger95c,
	author = {Karger, David R. and Klein, Philip N. and Tarjan, Robert E.},
	title = {A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees},
	year = {1995},
	issue_date = {March 1995},
	publisher = {Association for Computing Machinery},
	address = {New York, NY, USA},
	volume = {42},
	number = {2},
	journal = {J. ACM},
	pages = {321–328}
}

@article{Lovett19,
	Author = {Antonio Molina Lovett and Bryce Sandlund},
	Journal = {CoRR},
	Title = {A Simple Algorithm for Minimum Cuts in Near-Linear Time},
	Volume = {abs/1908.11829},
	Year = {2019}}

@inproceedings{Young95,
	Author = {Neal E. Young},
	Booktitle = {Proceedings of the 6th Annual Symposium on Discrete Algorithms.},
	Date-Added = {2020-02-14 17:32:47 -0500},
	Date-Modified = {2020-02-14 17:34:15 -0500},
	Title = {Randomized Rounding without solving the linear program},
	Year = {1995}}

@inproceedings{Thorup00,
	Author = {Mikkel Thorup and David R. Karger},
	Booktitle = {Proceedings of the 7th annual scandanavian symposium and workshops on algorithm theory},
	Date-Added = {2020-02-14 17:28:19 -0500},
	Date-Modified = {2020-02-14 17:30:27 -0500},
	Title = {Dynamic graph algorithms with applications},
	Year = {2000}}

@inproceedings{Mukhopadhyay19,
	Author = {Sagnik Mukhopadhyay and Danupon Nanongkai},
	Booktitle = {Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (to appear)},
	Date-Added = {2020-02-14 16:56:02 -0500},
	Date-Modified = {2020-02-14 16:59:32 -0500},
	Title = {Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms},
	Year = {2020}}

@inproceedings{Ghaffari20,
	Author = {Mohsen Ghaffari and Krzysztof Nowicki and Mikkel Thorup},
	Booktitle = {Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms},
	Date-Added = {2020-02-14 16:21:42 -0500},
	Date-Modified = {2020-02-14 16:23:49 -0500},
	Title = {Faster Algorithms for Edge Connectivity via Random $2$-Out Contractions},
	Year = {2020}}

@article{Gawrychowski19,
	Author = {Pawe{\l} Gawrychowski and Shay Mozes and Oren Weimann},
	Date-Added = {2019-11-12 18:12:46 -0500},
	Date-Modified = {2019-11-12 18:13:49 -0500},
	Journal = {CoRR},
	Title = {Minimum Cut in ${O}(m \log^2 n)$ Time},
	Volume = {abs/1911.01145},
	Year = {2019}}

@article{Nagamochi92b,
	Author = {Hiroshi Nagamochi and Toshihide Ibaraki},
	Date-Added = {2019-07-26 13:11:56 -0400},
	Date-Modified = {2019-07-26 13:12:50 -0400},
	Journal = {SIAM Journal on Discrete Mathematics},
	Number = {1},
	Pages = {54-66},
	Title = {Computing Edge-Connectivity in Multigraphs and Capacitated Graphs},
	Volume = {5},
	Year = {1992}}

@article{Nagamochi92a,
	Author = {Hiroshi Nagamochi and Toshihide Ibaraki},
	Date-Added = {2019-07-26 13:09:45 -0400},
	Date-Modified = {2019-07-26 13:10:52 -0400},
	Journal = {Algorithmica},
	Pages = {583-596},
	Title = {A linear-time algorithm for finding a sparse $k$-connected spanning subgraph of a $k$-connected graph},
	Volume = {7},
	Year = {1992}}

@inproceedings{Geissmann17,
	Author = {Geissmann, B. and Gianinazzi, L.},
	Booktitle = {International Conference on Algorithms and Complexity},
	Date-Added = {2019-07-25 15:57:15 -0400},
	Date-Modified = {2019-07-25 15:59:47 -0400},
	Title = {Cache Oblivious Minimum Cut},
	Year = {2017}}

@article{Karger99,
	Author = {David R. Karger},
	Date-Added = {2019-07-25 15:45:43 -0400},
	Date-Modified = {2019-07-25 15:47:00 -0400},
	Journal = {Mathematics of Operations Research},
	Number = {2},
	Title = {Random Sampling in Cut, Flow, and Network Design Problems},
	Volume = {24},
	Year = {1999}}

@article{Junger00,
	Author = {J{\"u}nger, M. and Rinaldi, G. and Thienel, S.},
	Date-Added = {2019-07-25 15:29:54 -0400},
	Date-Modified = {2019-07-25 15:31:41 -0400},
	Journal = {Algorithmica},
	Pages = {172},
	Title = {Practical Performance of Efficient Minimum Cut Algorithms},
	Volume = {26},
	Year = {2000}}

@mastersthesis{MT12,
	Author = {Sergey Kopeliovich},
	School = {Saint Petersburg State University},
	Title = {Offline solution of connectivity and $2$-edge-connectivity problems for fully dynamic graphs},
	Year = {2012}}

@inproceedings{HRT18,
	Author = {Jacob Holm and Eva Rotenberg and Mikkel Thorup},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Date-Added = {2018-04-18 08:44:54 +0000},
	Date-Modified = {2018-04-18 08:53:10 +0000},
	Title = {Dynamic bridge-finding in $\tilde{O}(\log^2 n)$ amortized time},
	Year = {2018}}

@phdthesis{Weiskircher02,
	Author = {Rene Weiskircher},
	Date-Added = {2017-07-05 22:37:18 +0000},
	Date-Modified = {2017-07-05 22:39:10 +0000},
	School = {Universit{\"a}t des Saarlandes},
	Title = {New Applications of SPQR-Trees in Graph Drawing},
	Year = {2002}}

@article{DurfeePPR17:arxiv,
	Author = {David Durfee and John Peebles and Richard Peng and Anup B. Rao},
	Journal = {CoRR},
	Title = {Determinant-Preserving Sparsification of {SDDM} Matrices with Applications to Counting and Sampling Spanning Trees},
	Volume = {abs/1705.00985},
	Year = {2017}}

@article{CohenMTV17:arxiv,
	Author = {Michael B. Cohen and Aleksander Madry and Dimitris Tsipras and Adrian Vladu},
	Journal = {CoRR},
	Title = {Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods},
	Volume = {abs/1704.02310},
	Year = {2017}}

@article{KrauthgamerR17,
	Author = {Robert Krauthgamer and Inbal Rika},
	Journal = {CoRR},
	Title = {Refined Vertex Sparsifiers of Planar Graphs},
	Volume = {abs/1702.05951},
	Year = {2017}}

@article{EnglertGKRTT14,
	Author = {Matthias Englert and Anupam Gupta and Robert Krauthgamer and Harald Racke and Inbal Talgam{-}Cohen and Kunal Talwar},
	Journal = {{SIAM} J. Comput.},
	Number = {4},
	Pages = {1239--1262},
	Title = {Vertex Sparsifiers: New Results from Old Techniques},
	Volume = {43},
	Year = {2014}}

@inproceedings{NanongkaiS17,
	Author = {Danupon Nanongkai and Thatchaphol Saranurak},
	Booktitle = {Proceedings of the 49th Annual {ACM}{SIGACT} Symposium on Theory of Computing},
	Pages = {1122--1129},
	Title = {Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and ${O}(n^{1/2 - \epsilon})$-time},
	Year = {2017}}

@inproceedings{Wulff-Nilsen17,
	Author = {Christian Wulff{-}Nilsen},
	Booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC}},
	Pages = {1130--1143},
	Title = {Fully-dynamic minimum spanning forest with improved worst-case update time},
	Year = {2017}}

@inproceedings{KargerP09,
	Author = {Karger, David R. and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Pages = {246--255},
	Title = {A near-linear time algorithm for constructing a cactus representation of minimum cuts},
	Year = {2009}}

@inproceedings{BhalgatHKP08,
	Author = {Bhalgat, Anand and Hariharan, Ramesh and Kavitha, Telikepalli and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms},
	Pages = {455--464},
	Title = {Fast edge splitting and Edmonds' arborescence construction for unweighted graphs},
	Year = {2008}}

@inproceedings{AbrahamDKKP16,
	Author = {I. {Abraham} and D. {Durfee} and I. {Koutis} and S. {Krinninger} and R. {Peng}},
	Booktitle = {2016 IEEE 57th Annual Symposium on Foundations of Computer Science},
	Issn = {0272-5428},
	Pages = {335-344},
	Title = {On Fully Dynamic Graph Sparsifiers},
	Year = {2016}}

@inproceedings{DurfeeKPRS17,
	Author = {David Durfee and Rasmus Kyng and John Peebles and Anup B. Rao and Sushant Sachdeva},
	Booktitle = {Proceedings of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing},
	Pages = {730--742},
	Title = {Sampling random spanning trees faster than matrix multiplication},
	Year = {2017}}

@article{GoranciHT16,
	Author = {Goranci, Gramoz and Henzinger, Monika and Thorup, Mikkel},
	Date-Added = {2020-02-14 15:32:04 -0500},
	Date-Modified = {2020-02-14 15:33:32 -0500},
	Journal = {ACM Transactions on Algorithms},
	Number = {2},
	Title = {Incremental Exact Min-Cut in Polylogarithmic Amortized Update},
	Volume = {14},
	Year = {2018}}

@inproceedings{AbboudWY15,
	Author = {Amir Abboud and Virginia Vassilevska Williams and Huacheng Yu},
	Booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory of Computing},
	Pages = {41--50},
	Title = {Matching Triangles and Basing Hardness on an Extremely Popular Conjecture},
	Year = {2015}}

@inproceedings{FungHHP11,
	Author = {Fung, Wai Shing and Hariharan, Ramesh and Harvey, Nicholas J.A. and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing},
	Pages = {71--80},
	Title = {A General Framework for Graph Sparsification},
	Year = {2011}}

@inproceedings{BenczurK96,
	Author = {Bencz\'{u}r, Andr\'{a}s A. and Karger, David R.},
	Booktitle = {Proceedings of the twenty-eighth annual ACM symposium on Theory of computing},
	Pages = {47--55},
	Title = {Approximating s-t minimum cuts in $\tilde{O}(n^2)$ time},
	Year = {1996}}

@inproceedings{HariharanKP07,
	Author = {Hariharan, Ramesh and Kavitha, Telikepalli and Panigrahi, Debmalya},
	Booktitle = {Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
	Pages = {127--136},
	Title = {Efficient algorithms for computing all low st edge connectivities and related problems},
	Year = {2007}}

@inproceedings{GalilI91,
	Author = {Galil, Zvi and Italiano, Giuseppe F},
	Booktitle = {Proceedings of the twenty-third annual ACM symposium on Theory of computing},
	Pages = {317--327},
	Title = {Fully dynamic algorithms for edge connectivity problems},
	Year = {1991}}

@article{Tsin09,
	Author = {Tsin, Yung H},
	Journal = {Journal of Discrete Algorithms},
	Number = {1},
	Pages = {130--146},
	Publisher = {Elsevier},
	Title = {Yet another optimal algorithm for 3-edge-connectivity},
	Volume = {7},
	Year = {2009}}

@article{HenzingerKing99,
	Author = {Monika Rauch Henzinger and Valerie King},
	Journal = {JOURNAL OF THE ACM},
	Pages = {516},
	Title = {Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation},
	Volume = {46},
	Year = {1999}}

@inproceedings{HolmLT98,
	Acmid = {276715},
	Address = {New York, NY, USA},
	Author = {Holm, Jacob and de Lichtenberg, Kristian and Thorup, Mikkel},
	Booktitle = {Proceedings of the thirtieth annual ACM symposium on Theory of computing},
	Isbn = {0-89791-962-9},
	Location = {Dallas, Texas, USA},
	Numpages = {11},
	Pages = {79--89},
	Publisher = {ACM},
	Series = {STOC '98},
	Title = {Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity},
	Year = {1998}}

@article{AlstrupHLT2005,
	Author = {Alstrup, Stephen and Holm, Jacob and Lichtenberg, Kristian De and Thorup, Mikkel},
	Journal = {ACM Trans. Algorithms},
	Number = {2},
	Pages = {243--264},
	Title = {Maintaining information in fully dynamic trees with top trees},
	Volume = {1},
	Year = {2005}}

@article{HopcroftT73,
	Author = {John E. Hopcroft and Robert Endre Tarjan},
	Journal = {{SIAM} J. Comput.},
	Number = {3},
	Pages = {135--158},
	Title = {Dividing a Graph into Triconnected Components},
	Volume = {2},
	Year = {1973}}

@inproceedings{DiBattistaT89,
	Acmid = {1398728},
	Address = {Washington, DC, USA},
	Author = {Di Battista, G. and Tamassia, R.},
	Booktitle = {Proceedings of the 30th Annual Symposium on Foundations of Computer Science},
	Isbn = {0-8186-1982-1},
	Keywords = {edge insertions, incremental planarity testing, planar graph, supports tests, insertion, vertices, edges, queries, vertex insertions},
	Numpages = {6},
	Pages = {436--441},
	Publisher = {IEEE Computer Society},
	Series = {SFCS '89},
	Title = {Incremental planarity testing},
	Year = {1989}}

@article{GomoryH61,
	Author = {Gomory, R. E. and Hu, T. C.},
	Journal = {Journal of the Society for Industrial and Applied Mathematics},
	Number = {4},
	Pages = {551--570},
	Title = {Multi-Terminal Network Flows},
	Volume = {9},
	Year = {1961}}

@article{Eppstein94,
	Acmid = {185278},
	Address = {Duluth, MN, USA},
	Author = {Eppstein, David},
	Issn = {0196-6774},
	Issue_Date = {Sept. 1994},
	Journal = {J. Algorithms},
	Month = sep,
	Number = {2},
	Numpages = {14},
	Pages = {237--250},
	Publisher = {Academic Press, Inc.},
	Title = {Offline algorithms for dynamic minimum spanning tree problems},
	Volume = {17},
	Year = {1994}}

@inproceedings{KaczmarzL15,
	Author = {Karczmarz, Adam and Lacki, Jakub},
	Booktitle = {Algorithms and Data Structures: 14th International Symposium, WADS 2015},
	Editor = {Dehne, Frank and Sack, Jorg-Rudiger and Stege, Ulrike},
	Pages = {458--469},
	Title = {Fast and Simple Connectivity in Graph Timelines},
	Year = {2015}}

@article{LackiS13,
	Author = {Jackub Lacki and Piotr Sankowski},
	Journal = {ITCS},
	Title = {Reachability in Graph Timelines},
	Year = {2013}}

@inproceedings{DemaineP04,
	Acmid = {1007435},
	Address = {New York, NY, USA},
	Author = {Patracscu, Mihai and Demaine, Erik D.},
	Booktitle = {Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
	Isbn = {1-58113-852-0},
	Keywords = {cell-probe complexity, dynamic connectivity, dynamic graph problems, lower bounds for data structures, partial sums problem},
	Location = {Chicago, IL, USA},
	Numpages = {8},
	Pages = {546--553},
	Publisher = {ACM},
	Series = {STOC '04},
	Title = {Lower bounds for dynamic connectivity},
	Year = {2004}}

@article{SleatorT85,
	Acmid = {2793},
	Address = {New York, NY, USA},
	Author = {Sleator, Daniel D. and Tarjan, Robert E.},
	Issn = {0001-0782},
	Issue_Date = {Feb. 1985},
	Journal = {Commun. ACM},
	Month = feb,
	Number = {2},
	Numpages = {7},
	Pages = {202--208},
	Publisher = {ACM},
	Title = {Amortized efficiency of list update and paging rules},
	Volume = {28},
	Year = {1985}}

@inproceedings{Fox11,
	Acmid = {2033225},
	Address = {Berlin, Heidelberg},
	Author = {Fox, Kyle},
	Booktitle = {Proceedings of the 12th international conference on Algorithms and data structures},
	Isbn = {978-3-642-22299-3},
	Location = {New York, NY},
	Numpages = {12},
	Pages = {411--422},
	Publisher = {Springer-Verlag},
	Series = {WADS'11},
	Title = {Upper bounds for maximally greedy binary search trees},
	Url = {http://dl.acm.org/citation.cfm?id=2033190.2033225},
	Year = {2011},
	Bdsk-Url-1 = {http://dl.acm.org/citation.cfm?id=2033190.2033225}}

@inproceedings{CharikarLSM10,
	Acmid = {1918391},
	Address = {Washington, DC, USA},
	Author = {Charikar, Moses and Leighton, Tom and Li, Shi and Moitra, Ankur},
	Booktitle = {Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science},
	Isbn = {978-0-7695-4244-7},
	Keywords = {vertex sparsifier, approximation algorithms},
	Numpages = {10},
	Pages = {265--274},
	Publisher = {IEEE Computer Society},
	Series = {FOCS '10},
	Title = {Vertex Sparsifiers and Abstract Rounding Algorithms},
	Year = {2010}}

@inproceedings{DiBattistaT90,
	Acmid = {92364},
	Address = {New York, NY, USA},
	Author = {Di Battista, Giuseppe and Tamassia, Roberto},
	Booktitle = {Proceedings of the seventeenth international colloquium on Automata, languages and programming},
	Isbn = {0-387-52826-1},
	Numpages = {14},
	Pages = {598--611},
	Title = {On-line graph algorithms with SPQR-trees},
	Year = {1990},
	Bdsk-Url-1 = {http://dl.acm.org/citation.cfm?id=90397.92364}}

@article{BienstockM88,
	Acmid = {45467},
	Address = {Philadelphia, PA, USA},
	Author = {Bienstock, Daniel and Monma, Clyde L.},
	Issn = {0097-5397},
	Issue_Date = {Feb. 1988},
	Journal = {SIAM J. Comput.},
	Month = feb,
	Number = {1},
	Numpages = {24},
	Pages = {53--76},
	Publisher = {Society for Industrial and Applied Mathematics},
	Title = {On the complexity of covering vertices by faces in a planar graph},
	Volume = {17},
	Year = {1988}}

@techreport{SaxeB79,
	Author = {Saxe, James B. and Bentley, Jon Louis.},
	Institution = {CMU},
	Number = {2420},
	Title = {Transforming static data structures to dynamic structures},
	Url = {http://repository.cmu.edu/compsci/2420},
	Year = {1979},
	Bdsk-Url-1 = {http://repository.cmu.edu/compsci/2420}}

@inproceedings{MillerR87,
	Author = {Gary L. Miller and Vijaya Ramachandran},
	Booktitle = {Combinatorica},
	Pages = {254--263},
	Title = {A new graph triconnectivity algorithm and its parallelization},
	Year = {1987}}

@inproceedings{EdwardsV12,
	Acmid = {2312042},
	Address = {New York, NY, USA},
	Author = {Edwards, James Alexander and Vishkin, Uzi},
	Booktitle = {Proceedinbgs of the 24th ACM symposium on Parallelism in algorithms and architectures},
	Isbn = {978-1-4503-1213-4},
	Keywords = {PRAM, graph algorithm, many-core, triconnected components},
	Location = {Pittsburgh, Pennsylvania, USA},
	Numpages = {3},
	Pages = {190--192},
	Publisher = {ACM},
	Series = {SPAA '12},
	Title = {Brief announcement: speedups for parallel graph triconnectivity},
	Year = {2012}}

@article{TarjanV85,
	Author = {Robert Endre Tarjan and Uzi Vishkin},
	Citedby = {0},
	Cites = {0},
	Journal = {SIAM J. Comput.},
	Number = {4},
	Pages = {862-874},
	Researchr = {http://researchr.org/publication/TarjanV85},
	Title = {An Efficient Parallel Biconnectivity Algorithm},
	Volume = {14},
	Year = {1985}}

@article{MillerR91,
	Author = {Gary L. Miller and John H. Reif},
	Journal = {SIAM JOURNAL ON COMPUTING},
	Number = {6},
	Pages = {1128--1147},
	Title = {Parallel Tree Contraction Part 2: Further Applications},
	Volume = {20},
	Year = {1991}}

@article{WestbrookT92,
	Author = {Westbrook, Jeffery and Tarjan, RobertE.},
	Issn = {0178-4617},
	Issue = {1-6},
	Journal = {Algorithmica},
	Keywords = {On-line algorithms; Graph algorithms; Graph connectivity; Dynamic trees; Data structures},
	Language = {English},
	Pages = {433-464},
	Publisher = {Springer-Verlag},
	Title = {Maintaining bridge-connected and biconnected components on-line},
	Volume = {7},
	Year = {1992}}

@inproceedings{KarczmarzL15,
	Author = {Adam Karczmarz and Jakub Lacki},
	Booktitle = {{WADS}},
	Pages = {458--469},
	Publisher = {Springer},
	Series = {Lecture Notes in Computer Science},
	Title = {Fast and Simple Connectivity in Graph Timelines},
	Volume = {9214},
	Year = {2015}}

@inproceedings{GoranciHP18:arxiv,
	Author = {Gramoz Goranci and Monika Henzinger and Pan Peng},
	Booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
	Pages = {40:1--40:15},
	Title = {Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs},
	Volume = {112},
	Year = {2018}}

@inproceedings{GoranciHP17,
	Author = {Gramoz Goranci and Monika Henzinger and Pan Peng},
	Booktitle = {European Symposium on Algorithms (ESA)},
	Pages = {45:1--45:14},
	Title = {The Power of Vertex Sparsifiers in Dynamic Graph Algorithms},
	Year = {2017}}

@article{LiPYZ18:arxiv,
	Author = {Huan Li and Stacy Patterson and Yuhao Yi and Zhongzhi Zhang},
	Journal = {CoRR},
	Title = {Maximizing the Number of Spanning Trees in a Connected Graph},
	Url = {https://arxiv.org/abs/1804.02785},
	Volume = {abs/1804.02785},
	Year = {2018},
	Bdsk-Url-1 = {https://arxiv.org/abs/1804.02785}}

@inproceedings{LiZ18,
	Author = {Li, Huan and Zhang, Zhongzhi},
	Booktitle = {Symposium on Discrete Algorithms (SODA)},
	Pages = {2377--2396},
	Title = {Kirchhoff Index As a Measure of Edge Centrality in Weighted Networks: Nearly Linear Time Algorithms},
	Year = {2018}}

@article{Karger00,
	Acmid = {331608},
	Address = {New York, NY, USA},
	Author = {Karger, David R.},
	Issn = {0004-5411},
	Issue_Date = {Jan. 2000},
	Journal = {J. ACM},
	Keywords = {Monte Carlo algorithm, connectivity, min-cut, optimization, tree packing},
	Month = jan,
	Number = {1},
	Numpages = {31},
	Pages = {46--76},
	Publisher = {ACM},
	Title = {Minimum Cuts in Near-linear Time},
	Volume = {47},
	Year = {2000}}

@article{Sleator83,
	Author = {Daniel D. Sleator and Robert Endre Tarjan},
	Journal = {Journal of Computer and System Sciences},
	Number = {3},
	Pages = {362 - 391},
	Title = {A data structure for dynamic trees},
	Volume = {26},
	Year = {1983}}

@article{Eppstein97,
	Acmid = {265914},
	Address = {New York, NY, USA},
	Author = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Nissenzweig, Amnon},
	Issn = {0004-5411},
	Issue_Date = {Sept. 1997},
	Journal = {J. ACM},
	Keywords = {dynamic graph algorithms, edge and vertex connectivity, minimum spanning trees},
	Month = sep,
	Number = {5},
	Numpages = {28},
	Pages = {669--696},
	Publisher = {ACM},
	Title = {Sparsification--A Technique for Speeding Up Dynamic Graph Algorithms},
	Volume = {44},
	Year = {1997}}

@inproceedings{Huang17,
	Acmid = {3039718},
	Author = {Huang, Shang-En and Huang, Dawei and Kopelowitz, Tsvi and Pettie, Seth},
	Booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Location = {Barcelona, Spain},
	Numpages = {11},
	Pages = {510--520},
	Title = {Fully Dynamic Connectivity in {$O(\log n(\log \log n)^2)$} Amortized Expected Time},
	Year = {2017}}

@inproceedings{Holm15,
	Abstract = {We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in O(log4				n/loglogn) expected amortized time per operation, improving the O(log4				n) amortized bound of Holm et al. (STOC '98, JACM '01). We also provide a deterministic data structure with amortized update time O(log4				n logloglogn/loglogn). We assume the Word-RAM model with standard instructions.},
	Address = {Berlin, Heidelberg},
	Author = {Holm, Jacob and Rotenberg, Eva and Wulff-Nilsen, Christian},
	Booktitle = {Algorithms - ESA 2015},
	Editor = {Bansal, Nikhil and Finocchi, Irene},
	Isbn = {978-3-662-48350-3},
	Pages = {742--753},
	Publisher = {Springer Berlin Heidelberg},
	Title = {Faster Fully-Dynamic Minimum Spanning Forest},
	Year = {2015}}

@inproceedings{Durfee19,
	Author = {Durfee, David and Gao, Yu and Goranci, Gramoz and Peng, Richard},
	Booktitle = {Proceedings of the thirtieth annual ACM symposium on Theory of computing},
	Publisher = {ACM},
	Series = {STOC '19},
	Title = {Fully Dynamic Spectral Vertex Sparsifiers and Applications},
	Year = {2019}}

@inproceedings{Eppstein06,
	Author = {Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Spencer, Thomas H.},
	Booktitle = {Siam Journal on Computing},
	Date-Added = {2019-02-20 22:03:46 +0000},
	Date-Modified = {2019-02-20 22:05:33 +0000},
	Title = {Separator-Based Sparsification II: edge and Vertex Connectivity},
	Year = {2006}}

@article{Goranci18,
	Author = {Gramoz Goranci and Monika Henzinger and Thatchaphol Saranurak},
	Date-Added = {2019-02-20 22:09:35 +0000},
	Date-Modified = {2019-02-20 22:13:11 +0000},
	Journal = {CoRR},
	Title = {Fast Incremental Algorithms via Local Sparsifiers},
	Url = {https://drive.google.com/file/d/1SJrbzuz\_szMwsBfeBZfGUWkDEbZKAGD5/view},
	Year = {2018},
	Bdsk-Url-1 = {https://drive.google.com/file/d/1SJrbzuz%5C_szMwsBfeBZfGUWkDEbZKAGD5/view}}

@inproceedings{Kratsch12,
	Author = {Kratsch, Stefan and Wahlstrom, Magnus},
	Booktitle = {Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science},
	Isbn = {978-0-7695-4874-6},
	Numpages = {10},
	Pages = {450--459},
	Series = {FOCS '12},
	Title = {Representative Sets and Irrelevant Vertices: New Tools for Kernelization},
	Year = {2012}}

@inproceedings{Assadi2015DynamicSF,
	Author = {Sepehr Assadi and Sanjeev Khanna and Yang Li and Val Tannen},
	Booktitle = {FSTTCS},
	Title = {Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches},
	Year = {2015}}

@inproceedings{Fafianie16,
	Author = {Stefan Fafianie and Stefan Kratsch and Vuong Anh Quyen},
	Booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
	Pages = {33:1--33:13},
	Title = {Preprocessing Under Uncertainty},
	Volume = {47},
	Year = {2016}}

@inproceedings{Fafianie16b,
	Author = {Stefan Fafianie and Eva-Maria C. Hols and Stefan Kratsch and Vuong Anh Quyen},
	Booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
	Pages = {35:1--35:14},
	Title = {Preprocessing Under Uncertainty: Matroid Intersection},
	Volume = {58},
	Year = {2016}}

@article{PengSS,
	Archiveprefix = {arXiv},
	Author = {Richard Peng and Bryce Sandlund and Daniel Dominic Sleator},
	Bibsource = {dblp computer science bibliography, https://dblp.org},
	Biburl = {https://dblp.org/rec/bib/journals/corr/abs-1708-03812},
	Eprint = {1708.03812},
	Journal = {CoRR},
	Timestamp = {Mon, 13 Aug 2018 16:49:10 +0200},
	Title = {Offline Dynamic Higher Connectivity},
	Url = {http://arxiv.org/abs/1708.03812},
	Volume = {abs/1708.03812},
	Year = {2017},
	Bdsk-Url-1 = {http://arxiv.org/abs/1708.03812}}

@misc{Molina19,
	Author = {Molina Lovett, Antonio J. and Sandlund, Bryce},
	Date = {2018-11-28},
	Howpublished = {personal communication}}

@inproceedings{Abboud16,
	Author = {Abboud, Amir and Dahlgaard, Soren},
	Booktitle = {IEEE 57th Annual Symposium on Foundations of Computer Science},
	Month = {10},
	Pages = {477-486},
	Title = {Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms},
	Year = {2016}}

@inproceedings{Dahlgaard16,
	Author = {Dahlgaard, Soren},
	Booktitle = {43rd International Colloquium on Automata, Languages, and Programming},
	Date-Added = {2019-02-20 23:36:01 +0000},
	Date-Modified = {2019-02-21 00:02:41 +0000},
	Title = {On the hardness of partially dynamic graph problems and connections to diameter},
	Year = {2016}}

@article{Bringmann18,
	Author = {Karl Bringmann and Marvin Kunnemann and Andre Nusser},
	Journal = {CoRR},
	Title = {Frechet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability},
	Url = {https://arxiv.org/abs/1810.10982},
	Volume = {abs/1810.10982},
	Year = {2018},
	Bdsk-Url-1 = {https://arxiv.org/abs/1810.10982}}

@article{Gabow91,
	Author = {H.N. Gabow},
	Issn = {0022-0000},
	Journal = {Journal of Computer and System Sciences},
	Number = {2},
	Pages = {259 - 273},
	Title = {A Matroid Approach to Finding Edge Connectivity and Packing Arborescences},
	Volume = {50},
	Year = {1995}}

@inproceedings{Plotkin92,
	Author = {S. A. {Plotkin} and D. B. {Shmoys} and E. {Tardos}},
	Booktitle = {Proceedings 32nd Annual Symposium of Foundations of Computer Science},
	Pages = {495-504},
	Title = {Fast approximation algorithms for fractional packing and covering problems},
	Year = {1991}}

@inproceedings{Karger93a,
	Author = {Karger, David R.},
	Booktitle = {Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Pages = {21--30},
	Series = {SODA '93},
	Title = {Global Min-cuts in {RNC}, and Other Ramifications of a Simple Min-out Algorithm},
	Year = {1993}}

@article{Thorup07,
	Author = {Thorup, Mikkel},
	Journal = {Combinatorica},
	Number = {1},
	Pages = {91--127},
	Title = {Fully-Dynamic Min-Cut*},
	Volume = {27},
	Year = {2007}}

@inproceedings{Chekuri97,
	Author = {Chekuri, Chandra S. and Goldberg, Andrew V. and Karger, David R. and Levine, Matthew S. and Stein, Cliff},
	Booktitle = {Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Pages = {324--333},
	Title = {Experimental Study of Minimum Cut Algorithms},
	Year = {1997}}

@article{Henzinger18,
	Author = {Henzinger, Monika and Noe, Alexander and Schulz, Christian and Strash, Darren},
	Journal = {J. Exp. Algorithmics},
	Pages = {1.8:1--1.8:22},
	Title = {Practical Minimum Cut Algorithms},
	Volume = {23},
	Year = {2018}}

@inproceedings{Chalermsook04,
	Author = {Chalermsook, Parinya and Fakcharoenphol, Jittat and Nanongkai, Danupon},
	Booktitle = {Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Pages = {828--829},
	Title = {A Deterministic Near-linear Time Algorithm for Finding Minimum Cuts in Planar Graphs},
	Year = {2004}}

@inproceedings{Ghaffari13,
	Author = {Ghaffari, Mohsen and Kuhn, Fabian},
	Booktitle = {International Symposium on Distributed Computing},
	Pages = {1--15},
	Title = {Distributed Minimum Cut Approximation},
	Year = {2013}}

@inproceedings{Geissmann18,
	Author = {Geissmann, Barbara and Gianinazzi, Lukas},
	Booktitle = {Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures},
	Pages = {1--11},
	Title = {Parallel Minimum Cuts in Near-linear Work and Low Depth},
	Year = {2018}}

@article{Kawarabayashi19,
	Author = {Kawarabayashi, Ken-Ichi and Thorup, Mikkel},
	Journal = {J. ACM},
	Pages = {4:1--4:50},
	Title = {Deterministic Edge Connectivity in Near-Linear Time},
	Volume = {66},
	Year = {2018}}

@inproceedings{Henzinger17,
	Author = {Monika Henzinger and Satish Rao and Di Wang},
	Booktitle = {Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Pages = {1919-1938},
	Title = {Local Flow Partitioning for Faster Edge Connectivity},
	Year = {2017}}

@inproceedings{Daga19,
	Author = {Daga, Mohit and Henzinger, Monika and Nanongkai, Danupon and Saranurak, Thatchaphol},
	Booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing},
	Pages = {343--354},
	Title = {Distributed Edge Connectivity in Sublinear Time},
	Year = {2019}}

@inproceedings{Nanongkai14,
	Author = {Danupon Nanongkai and Hsin-Hao Su},
	Booktitle = {International Symposium on Distributed Computing},
	Title = {Almost-Tight Distributed Minimum Cut Algorithms},
	Year = {2014}}

@article{Stoer97,
	Author = {Stoer, Mechthild and Wagner, Frank},
	Journal = {J. ACM},
	Number = {4},
	Pages = {585--591},
	Title = {A Simple Min-cut Algorithm},
	Volume = {44},
	Year = {1997}}

@article{Ramanathan87,
	Author = {Ramanathan, Aparna and J. Colbourn, Charles},
	Journal = {Mathematical Programming},
	Pages = {253-261},
	Title = {Counting almost minimum cutsets with reliability applications},
	Volume = {39},
	Year = {1987}}

@inproceedings{Karger95,
	Author = {Karger, David R.},
	Booktitle = {Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing},
	Pages = {11--17},
	Title = {A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem},
	Year = {1995}}

@inproceedings{Botafogo93,
	Author = {Botafogo, Rodrigo A.},
	Booktitle = {Proceedings of the 16th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval},
	Pages = {116--125},
	Publisher = {ACM},
	Series = {SIGIR '93},
	Title = {Cluster Analysis for Hypertext Systems},
	Year = {1993}}

@book{Applegate07,
	Address = {Princeton, NJ, USA},
	Author = {Applegate, David L. and Bixby, Robert E. and Chvatal, Vasek and Cook, William J.},
	Isbn = {0691129932, 9780691129938},
	Publisher = {Princeton University Press},
	Title = {The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics)},
	Year = {2007}}

@article{Karger96,
	Author = {Karger, David R. and Stein, Clifford},
	Journal = {J. ACM},
	Number = {4},
	Pages = {601--640},
	Title = {A New Approach to the Minimum Cut Problem},
	Volume = {43},
	Year = {1996}}

@article{Hao94,
	Author = {J.X. Hao and J.B. Orlin},
	Journal = {Journal of Algorithms},
	Number = {3},
	Pages = {424 - 446},
	Title = {A Faster Algorithm for Finding the Minimum Cut in a Directed Graph},
	Volume = {17},
	Year = {1994}}

@article{Fredman87,
	Author = {Fredman, Michael L. and Tarjan, Robert Endre},
	Journal = {J. ACM},
	Number = {3},
	Pages = {596--615},
	Title = {Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms},
	Volume = {34},
	Year = {1987}}

@article{NashWilliams61,
	Author = {Nash-Williams, C. St.J. A.},
	Journal = {Journal of the London Mathematical Society},
	Number = {1},
	Pages = {445-450},
	Title = {{Edge-Disjoint Spanning Trees of Finite Graphs}},
	Volume = {s1-36},
	Year = {1961}}

@inproceedings{Tarjan05,
	Author = {Tarjan, Robert E. and Werneck, Renato F.},
	Booktitle = {Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Pages = {813--822},
	Title = {Self-adjusting Top Trees},
	Year = {2005}}

@inproceedings{Matula93,
	Author = {Matula, David W.},
	Booktitle = {Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms},
	Pages = {500--504},
	Title = {A Linear Time $2 + \epsilon$ Approximation Algorithm for Edge Connectivity},
	Year = {1993}}

@phdthesis{Karger95b,
	Address = {Stanford, CA, USA},
	Author = {Karger, David Ron},
	Note = {UMI Order No. GAX95-16851},
	Publisher = {Stanford University},
	School = {Stanford University},
	Title = {Random Sampling in Graph Optimization Problems},
	Year = {1995}}

@article{Kruskal56,
	Author = {Joseph B. Kruskal},
	Journal = {Proceedings of the American Mathematical Society},
	Number = {1},
	Pages = {48--50},
	Title = {On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem},
	Volume = {7},
	Year = {1956}}