Loading...
Please wait, while we are loading the content...
Similar Documents
On the Query Complexity of Testing for Eulerian Orientations
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fischer, Eldar Matsliah, Arie Newman, Ilan Yahalom, Orly |
| Copyright Year | 2009 |
| Abstract | We consider testing directed graphs for being Eulerian in the orientation model introduced in [15]. Despite the local nature of the property of being Eulerian, it turns out to be significantly harder for testing than other properties studied in the orientation model. We show a superconstant 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 sub-linear 2-sided test for general graphs. For special classes of graphs, including bounded-degree graphs and expander graphs, we provide improved results. In particular, for dense graphs we give a 2-sided test with constant query complexity. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.technion.ac.il/~ariem/papers/euler.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
