Testing subgraphs in directed graphs

DOI10.1145/780542.780644zbMath1192.68338OpenAlexW2090798615MaRDI QIDQ5901094

Asaf Shapira, Noga Alon

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Packing directed cycles efficiently ⋮ Packing edge-disjoint triangles in regular and almost regular tournaments ⋮ Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs ⋮ Almost given length cycles in digraphs ⋮ Testing subgraphs in directed graphs ⋮ Forcing large transitive subtournaments

This page was built for publication: Testing subgraphs in directed graphs