David Eppstein - Publications

Publications with J. Michael McCarthy

• Automated generation of linkage loop equations for planar 1-dof linkages, demonstrated up to 8-bar.
  B. E. Parrish, J. M. McCarthy, and D. Eppstein.
  Proc. ASME 2014 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, Vol. 5A: 38th Mechanisms and Robotics Conference, Buffalo, New York, USA, August 17-20, 2014, paper no. DETC2014-35263.
  J. Mechanisms and Robotics 7 (1): 011006, 2015.

  This paper reports on an implementation of an algorithm for constructing the configuration space of two-dimensional linkages with one degree of freedom.

  (eScholarship conference version – eScholarship journal version)

• Rooted cycle bases.
  D. Eppstein, J. M. McCarthy, and B. E. Parrish.
  arXiv:1504.04931.
  14th Algorithms and Data Structures Symp. (WADS 2015), Victoria, BC.
  Springer, Lecture Notes in Comp. Sci. 9214 (2015), pp. 339–350.
  J. Graph Algorithms & Applications 21 (4): 663–686, 2017.

  We consider the problem of finding a cycle basis for a graph in which all basis cycles contain a specified edge. We characterize the graphs having such a basis in terms of their vertex connectivity, we show that the minimum weight cycle basis with this constraint can be found in polynomial time and is weakly fundamental, and we show that finding a fundamental cycle basis with this constraint is NP-hard but fixed-parameter tractable.

  (Slides)

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.