Can hospitals afford digital storage for imagery?
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
We consider testing directed graphs Eulerianity in the orientation model introduced in Halevy et al. [2005]. Despite the local nature of the Eulerian property, it turns out to be significantly harder to test than other properties studied in the orientation model. We show a nonconstant lower bound on the query complexity of 2-sided tests and a linear lower bound on the query complexity of 1-sided tests for this property. On the positive side, we give several 1-sided and 2-sided tests, including a sublinear query complexity 2-sided test, for general graphs. For special classes of graphs, including bounded-degree graphs and expander graphs, we provide improved results. In particular, we give a 2-sided test with constant query complexity for dense graphs, as well as for expander graphs with a constant expansion parameter. © 2012 ACM.
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University