Covering Graphs with Few Complete Bipartite Subgraphs

DOI10.1007/978-3-540-77050-3_28MaRDI QIDQ5458846zbMATH OpenOpenAlexFDO

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

Publication date 24 April 2008

Published in FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77050-3_28

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Covering graphs with few complete bipartite subgraphs
• On the parameterized complexity of biclique cover and partition
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
• Polynomially solvable cases of the minimum biclique vertex-cover problem
• The parameterized complexity of the \(k\)-biclique problem

Cites work

• scientific article; zbMATH DE number 2131198 (Why is no real title available?)
• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Chromatic characterization of biclique covers
• Complexity of list coloring problems with a fixed total number of colors
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Computational Complexity of Compaction to Reflexive Cycles
• Data reduction, exact, and heuristic algorithms for clique cover
• FindingH-partitions efficiently
• On edge perfectness and classes of bipartite graphs
• Parametrized complexity theory.

Cited in

(15)

• Bi-covering: covering edges with two small subsets of vertices
• Efficient approximation for restricted biclique cover problems
• Chromatic characterization of biclique covers
• Nearly tight approximability results for minimum biclique cover and partition
• Polynomially solvable cases of the minimum biclique vertex-cover problem
• Covering graphs with few complete bipartite subgraphs
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
• The parameterized complexity of the \(k\)-biclique problem
• The parameterized complexity of \(k\)-biclique
• Linear time algorithm for computing a small biclique in graphs without long induced paths
• Bicovering: covering edges with two small subsets of vertices
• Problems and invariants connected with bicliques and multicliques of graphs
• On the parameterized complexity of biclique cover and partition
• scientific article; zbMATH DE number 175738 (Why is no real title available?)
• Bipartite Coverings of Graphs

This page was built for publication: Covering Graphs with Few Complete Bipartite Subgraphs

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