Testing whether a digraph contains H-free k-induced subgraphs

DOI10.1016/J.TCS.2008.08.033MaRDI QIDQ955032zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• scientific article; zbMATH DE number 6469238
• Testing subgraphs in directed graphs
• Testing subgraphs in directed graphs
• Testing subgraphs in large graphs
• Property testing in sparse directed graphs: strong connectivity and subgraph-freeness

Cites work

• scientific article; zbMATH DE number 3558963 (Why is no real title available?)
• scientific article; zbMATH DE number 3557238 (Why is no real title available?)
• scientific article; zbMATH DE number 1775411 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)
• A combinatorial characterization of the testable graph properties, it's all about regularity
• A sublinear bipartiteness tester for bounded degree graphs
• Balanced coloring of bipartite graphs
• Complete subgraphs are elusive
• Efficient testing of large graphs
• On a problem of K. Zarankiewicz
• On the time required to detect cycles and connectivity in graphs
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing monotonicity
• Testing problems with sublearning sample complexity
• Testing subgraphs in directed graphs
• Testing versus estimation of graph properties
• Tolerant property testing and distance approximation
• Tolerant versus intolerant testing for Boolean properties

Cited in

(3)

• Testing subgraphs in directed graphs
• Testing subgraphs in directed graphs
• scientific article; zbMATH DE number 6469238 (Why is no real title available?)

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

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