Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects

DOI10.1007/978-3-540-74208-1_34MaRDI QIDQ3603487zbMATHOpenAlexFDO

Authors Eldar Fischer, Eyal Rozenberg

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_34

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hypergraphs (05C65)

Recommendations

• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Forbidden induced subgraphs for bounded \(p\)-intersection number
• A sublinear bipartiteness tester for bounded degree graphs
• scientific article; zbMATH DE number 1775414
• Tight Bounds for Testing Bipartiteness in General Graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Near-complete multipartite graphs and forbidden induced subgraphs
• Forbidden induced subgraphs for near perfect matchings

Cited in

(5)

• Earthmover Resilience and Testing in Ordered Structures
• scientific article; zbMATH DE number 1775414 (Why is no real title available?)
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Efficient removal lemmas for matrices
• Efficient removal lemmas for matrices

This page was built for publication: Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects

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