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

DOI10.1007/978-3-540-74208-1_34zbMATH Open1171.05374OpenAlexW1838671497MaRDI QIDQ3603487FDOQ3603487

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

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

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)

Cited In (5)

• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Earthmover Resilience and Testing in Ordered Structures
• Title not available (Why is that?)
• 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)