David Eppstein – Publications

Publications with Jean-Claude Falmagne

Algorithms for media.
D. Eppstein and J.-C. Falmagne.
arXiv:cs.DS/0206033.
Int. Conf. Ordinal and Symbolic Data Analysis, Irvine, 2003.
Discrete Applied Mathematics 156 (8): 1308–1320, 2008, doi:10.1016/j.dam.2007.05.035.

Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientations, and many other familiar structures. We find efficient solutions for several algorithmic problems on media: finding short reset sequences, shortest paths, testing whether a medium has a closed orientation, and listing the states of a medium given a black-box description.

(OSDA talk slides)

On verifying and engineering the well-gradedness of a union-closed family.
D. Eppstein, J.-C. Falmagne, and H. Uzun.
arXiv:0704.2919.
38th Meeting of the European Mathematical Psychology Group, Luxembourg, 2007.
J. Mathematical Psychology 53 (1): 34–39, 2009, doi:10.1016/j.jmp.2008.09.002.

We describe tests for whether the union-closure of a set family is well-graded, and algorithms for finding a minimal well-graded union-closed superfamily of a given set family.

Media Theory: Interdisciplinary Applied Mathematics.
D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov.
Springer, 2007, ISBN 978-3-540-71696-9.

Many combinatorial structures such as the set of acyclic orientations of a graph, weak orderings of a set of elements, or chambers of a hyperplane arrangement have the structure of a partial cube, a graph in which vertices may be labeled by bitvectors in such a way that graph distance equals Hamming distance. This book analyzes these structures in terms of operations that change one vertex to another by flipping a single bit of the bitvector labelings. It incorporates material from several of my papers including "Algorithms for media", "Algorithms for drawing media", "Upright-quad drawing of st-planar learning spaces", and "The Lattice dimension of a graph".

(Publisher's web site – Reinhard Suck's review in J. Math. Psych. – Reinhard Suck's review in MathSciNet)

Knowledge Spaces: Applications in Education.
J.-C. Falmagne, D. Albert, C. Doble, D. Eppstein, and X. Hu, eds.
Springer, 2013, doi:10.1007/978-3-642-35329-1.

This edited volume collects experiences with automated learning systems based on the theory of knowledge spaces, and mathematical explorations of the theory of knowledge spaces and their efficient implementation.