**Finding the**.*k*smallest spanning trees

D. Eppstein.

*2nd Scand. Worksh. Algorithm Theory,*Bergen, Norway, 1990.

Springer,*Lecture Notes in Comp. Sci.*447, 1990, pp. 38–47.

*BIT*32: 237–248, 1992 (special issue for 2nd Scand. Worksh. Algorithm Theory).By removing edges not involved in some solution, and contracting edges involved in all solutions, we reduce the problem to one in a graph with O(

*k*) edges and vertices. This simplification step transforms any time bound involving*m*or*n*to one involving min(*m,**k*) or min(*n,**k*) respectively. This paper also introduces the geometric version of the*k*smallest spanning trees problem (the graph version was long known) which it solves using order (*k*+1) Voronoi diagrams.(BibTeX – Citations – ACM DL (SWAT) – ACM DL (BIT))

**Using sparsification for parametric minimum spanning tree problems**.

D. Fernández-Baca, G. Slutzki, and D. Eppstein.

*5th Scand. Worksh. Algorithm Theory,*Reykjavik, 1996.

Springer,*Lecture Notes in Comp. Sci.*1097, 1996, pp. 149–160.

*Nordic J. Computing*3 (4): 352–366, 1996 (special issue for 5th SWAT).Given a graph with edge weights that are linear functions of a parameter, finds the sequence of minimum spanning trees produced as the parameter varies, in total time O(mn log n), by combining ideas from "Sparsification" and "Geometric lower bounds". Also solves various problems of optimizing the parameter value, including one closely related to that in "Choosing subsets with maximum weighted average".

(BibTeX – Citations – MIT hypertext bibliography – ACM DL (SWAT) – ACM DL (NJC))

**The weighted maximum-mean subtree and other bicriterion subtree problems.**

J. Carlson and D. Eppstein.

arXiv:cs.CG/0503023.

*Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006)*.

Springer,*Lecture Notes in Comp. Sci.*4059, 2006, pp. 397–408.We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".

(BibTeX)

**Cuckoo filter: simplification and analysis**.

D. Eppstein.

arXiv:1604.06067.

*Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)*, Reykjavik, Iceland.

Leibniz International Proceedings in Informatics (LIPIcs) 53, pp. 8.1–8.12.A cuckoo filter is an approximate set data structure that can be used in place of a Bloom filter, but with several practical advantages: it uses less space, has better locality of reference, and can handle element deletions. We provide the first theoretical analysis of a simplified variation of cuckoo filters, showing that these advantages can be guaranteed to hold theoretically and not just experimentally.

(Slides)

Conferences – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.