MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

On Biclique Cover and Partition of Bipartite Graphs

Tetiana Lavynska
Otto-von-Guericke-Universität Magdeburg
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Thursday, 14 December 2017
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

 


Two well-known NP-complete problems for bipartite graphs are considered: biclique cover and biclique partition problems. These problems have applications in many fields of computer science, e.g., optimization of OLED displays, automata theory, computer security and role minimization in role-based access control systems. Moreover, a biclique cover number and a biclique partition number have direct connections to Boolean and binary ranks of binary matrices.

In this talk, I will show the upper bound on the biclique partition number in terms of the biclique cover number. I will also present results on the complexity of the biclique cover and the biclique partition problems for special graph classes. Finally, the results about binary rank of Kronecker product and the connected open question will be discussed.

Contact

Yun Kuen Cheung
--email hidden
passcode not visible
logged in users only

Yun Kuen Cheung, 12/12/2017 21:15
Yun Kuen Cheung, 12/12/2017 21:10 -- Created document.