On the query complexity of testing orientations for being Eulerian

DOI10.1145/2151171.2151178MaRDI QIDQ3189056zbMATH OpenOpenAlexFDO

Authors 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

Eulerian orientationsgraph algorithmsmassively parameterizedproperty testing

Mathematics Subject Classification ID

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

Recommendations

• On the Query Complexity of Testing Orientations for Being Eulerian
• Testing Eulerianity and connectivity in directed sparse graphs
• Property testing in bounded degree graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• Testing subgraphs in directed graphs

Cited in

(7)

• Non-interactive proofs of proximity
• Testing whether the uniform distribution is a stationary distribution
• Testing list H-homomorphisms
• On the Query Complexity of Testing Orientations for Being Eulerian
• The subgraph testing model
• Testing uniformity of stationary distribution
• Testing Eulerianity and connectivity in directed sparse graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189056)