×

The biclique covering number of grids. (English) Zbl 1427.05174

Summary: We determine the exact value of the biclique covering number for all grid graphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Software:

SCIP
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Noga Alon, Neighborly families of boxes and bipartite coverings, The Mathematics of Paul Erd¨os II, Springer Berlin Heidelberg, Berlin, Heidelberg, 1997, pp. 27-31. · Zbl 0863.05065
[2] Manuel Aprile, Yuri Faenza, Samuel Fiorini, Tony Huynh, and Marco Macchia, Extension complexity of stable set polytopes of bipartite graphs, Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., vol. 10520, Springer, Cham, 2017, pp. 75-87. MR 3746146 · Zbl 1483.90129
[3] Sergei Bezrukov, Dalibor Fronˇcek, Steven J. Rosenberg, and Petr Kov´aˇr, On biclique coverings, Discrete Math. 308 (2008), no. 2-3, 319-323. MR 2378030 · Zbl 1135.05057
[4] Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, and Andreas Karrenbauer, Nearly tight approximability results for minimum biclique cover and partition, Algorithms—ESA 2014, Lecture Notes in Comput. Sci., vol. 8737, Springer, Heidelberg, 2014, pp. 235-246. MR 3253135 · Zbl 1423.68590
[5] Peter C. Fishburn and Peter L. Hammer, Bipartite dimensions and bipartite degrees of graphs, Discrete Math. 160 (1996), no. 1-3, 127-148. MR 1417566 · Zbl 0861.05035
[6] Dalibor Fronˇcek, Janja Jerebic, Sandi Klavˇzar, and Petr Kov´aˇr, Strong isometric dimension, biclique coverings, and Sperner’s theorem, Combin. Probab. Comput. 16 (2007), no. 2, 271-275. MR 2298814 · Zbl 1122.05033
[7] Michael R. Garey and David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979, A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences. MR 519066 · Zbl 0411.68039
[8] Ambros Gleixner, Michael Bastubbe, Leon Eifler, Tristan Gally, Gerald Gamrath, Robert Lion Gottwald, Gregor Hendel, Christopher Hojny, Thorsten Koch, Marco E. L¨ubbecke, Stephen J. Maher, Matthias Miltenberger, Benjamin M¨uller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Franziska Schl¨osser, Christoph Schubert, Felipe Serrano, Yuji Shinano, Jan Merlin Viernickel, Matthias Walter, Fabian Wegscheider, Jonas T. Witt, and Jakob Witzig, The SCIP Optimization Suite 6.0, Technical report, Optimization Online, July 2018.
[9] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495-2519. MR 0289210 · Zbl 0228.94020
[10] Volker Kaibel and Stefan Weltge, A short proof that the extension complexity of the correlation polytope grows exponentially, Discrete Comput. Geom. 53 (2015), no. 2, 397-401. MR 3316228 · Zbl 1315.52021
[11] Dana S. Nau, George Markowsky, Max A. Woodbury, and D. Bernard Amos, A mathematical analysis of human leukocyte antigen serology, Math. Biosci. 40 (1978), no. 3-4, 243-270. MR 503830 · Zbl 0394.92007
[12] A. A. Razborov, Applications of matrix methods to the theory of lower bounds in computational complexity, Combinatorica 10 (1990), no. 1, 81-93. MR 1075069 · Zbl 0717.68049
[13] F. Moazami, Biclique cover and local clique cover of graphs, Bull. Iranian Math. Soc. 44 (2018), no. 1, 225-235. · Zbl 1409.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.