Covering graphs with few complete bipartite subgraphs

DOI10.1016/j.tcs.2008.12.059zbMath1168.68019OpenAlexW2166502815MaRDI QIDQ1019181

Daniël Paulusma, Stefan Szeider, Egbert Mujuni, Herbert Fleischner

Publication date: 28 May 2009

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

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

zbMATH Keywords

bicliquesparameterized complexitycovering and partitioning problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Coloring problems on bipartite graphs of small diameter, Unnamed Item, Unnamed Item, Disconnected cuts in claw-free graphs, VNS matheuristic for a bin packing problem with a color constraint, Order-sensitive domination in partially ordered sets and graphs, Mod/Resc parsimony inference: theory and application, Unnamed Item, Unnamed Item, The complexity of surjective homomorphism problems-a survey, Unnamed Item, Parameterizing cut sets in a graph by the number of their components, ON AN INVARIANT FOR THE PROBLEM OF UNDERDETERMINED DATA DECOMPOSING, Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees, Coherent network partitions: characterizations with cographs and prime graphs, The computational complexity of disconnected cut and \(2 K_2\)-partition, Computing vertex-surjective homomorphisms to partially reflexive trees, On disconnected cuts and separators, Coherent network partitions, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Graph partitions with prescribed patterns, Efficient approximation for restricted biclique cover problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On miniaturized problems in parameterized complexity theory
• Bipartite dimensions and bipartite degrees of graphs
• A mathematical analysis of human leukocyte antigen serology
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Complexity of list coloring problems with a fixed total number of colors
• On edge perfectness and classes of bipartite graphs
• Chromatic characterization of biclique covers
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
• Minimal NFA Problems are Hard
• FindingH-partitions efficiently
• Computational Complexity of Compaction to Reflexive Cycles
• Data Reduction, Exact, and Heuristic Algorithms for Clique Cover