3 papers
cs.DS2020
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
Chandra Chekuri, Kent Quanrud, Manuel R. Torres
We develop fast approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem (BD-MST) and its generalization the Crossing Spanning Tree problem (Crossing…
cs.CG2018
Geometric Fingerprint Recognition via Oriented Point-Set Pattern Matching
David Eppstein, Michael T. Goodrich, Jordan Jorgensen +1
Motivated by the problem of fingerprint matching, we present geometric approximation algorithms for matching a pattern point set against a background point set, where the points ha…
cs.MM2016
Models and Algorithms for Graph Watermarking
David Eppstein, Michael T. Goodrich, Jenny Lam +3
We introduce models and algorithmic foundations for graph watermarking. Our frameworks include security definitions and proofs, as well as characterizations when graph watermarking…