David Eppstein - Publications

Publications with Vijay V. Vazirani

• NC algorithms for perfect matching and maximum flow in one-crossing-minor-free graphs.
  D. Eppstein and V. V. Vazirani.
  arXiv:1802.00084.
  Proc. 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), Phoenix, Arizona, 2019, pp. 23–30.
  SIAM J. Computing 50 (3): 1014–1033, 2021.

  We extend Anari and Vazirani's parallel algorithm for perfect matching in planar graphs to the graph families with a forbidden minor with crossing number one, by developing a concept of mimicking networks for perfect matching.

  (Slides)