Scandinavian Worksh. Algorithm Theory (SWAT)
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.
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".
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".
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.
Simplifying activity-on-edge graphs.
D. Eppstein, D. Frishberg, and E. Havvaei.
arXiv:2002.01610.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 24:1–24:14.Given a partially ordered set of activities, we find in polynomial time a directed acyclic graph and a mapping from activities to its edges, such that the sequences of activities along paths in the graph are exactly the totally ordered subsets of activities in the input.
Low-stretch spanning trees of graphs with bounded width.
G. Borradaile, E. Chambers, D. Eppstein, W. Maxwell, and A. Nayyeri.
arXiv:2004.08375.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020).
Leibniz International Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19.We describe a random distribution on the spanning trees of bounded-bandwidth graphs such that each edge has bounded expected stretch, along with several related results for other kinds of graph widths.