On the query complexity of testing orientations for being Eulerian

DOI10.1145/2151171.2151178zbMath1295.68132OpenAlexW2153563062MaRDI QIDQ3189056

Eldar Fischer, Oded Lachish, Arie Matsliah, Ilan Newman, Orly Yahalom

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2151171.2151178

zbMATH Keywords

graph algorithmsproperty testingEulerian orientationsmassively parameterized

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (3)

Testing list \(H\)-homomorphisms ⋮ Non-interactive proofs of proximity ⋮ Unnamed Item

This page was built for publication: On the query complexity of testing orientations for being Eulerian