Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs

DOI10.1016/J.TCS.2008.08.033zbMath1153.68040OpenAlexW2069646494MaRDI QIDQ955032

Hong-Yiu Lin, Yen-Wu Ti, Yuh-Dauh Lyuu, Tak-Man Ma

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.033

zbMATH Keywords

randomized algorithmdirected graphsproperty testing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complete subgraphs are elusive
• A sublinear bipartiteness tester for bounded degree graphs
• Tolerant property testing and distance approximation
• A combinatorial characterization of the testable graph properties
• Balanced coloring of bipartite graphs
• Property testing and its connection to learning and approximation
• Testing versus estimation of graph properties
• Robust Characterizations of Polynomials with Applications to Program Testing
• On the time required to detect cycles and connectivity in graphs
• On a problem of K. Zarankiewicz
• Testing subgraphs in directed graphs
• Testing problems with sublearning sample complexity
• Testing monotonicity
• Efficient testing of large graphs

This page was built for publication: Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs