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.

  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.

  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.

  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.