ALGORITHMS FOR MEDIA
David Eppstein and Jean-Claude Falmagne
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.