On the Query Complexity of Testing Orientations for Being Eulerian

DOI10.1007/978-3-540-85363-3_32zbMath1159.68471OpenAlexW2173642833MaRDI QIDQ3541809

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

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_32

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (6)

Testing whether the uniform distribution is a stationary distribution ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Testing convexity properties of tree colorings ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ Proximity Oblivious Testing and the Role of Invariances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eulerian graphs and related topics. Part 1, Volume 1
• Eulerian graphs and related topics. Part 1, Volume 2
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• Self-testing/correcting with applications to numerical problems
• Handbook of randomized computing. Vols. 1, 2
• On the number of Eulerian orientations of a graph
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• On the diameter of Eulerian orientations of graphs
• Testing Convexity Properties of Tree Colorings
• Testing st-Connectivity
• On some connectivity properties of Eulerian graphs
• Testing the diameter of graphs
• Testing properties of directed graphs: acyclicity and connectivity*
• An Eulerian path approach to DNA fragment assembly
• Tight Bounds for Testing Bipartiteness in General Graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Some 3CNF Properties Are Hard to Test
• Testing subgraphs in directed graphs
• Property testing in bounded degree graphs

This page was built for publication: On the Query Complexity of Testing Orientations for Being Eulerian