Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On Biclique Cover and Partition of Bipartite Graphs
Speaker:Tetiana Lavynska
coming from:Otto-von-Guericke-Universität Magdeburg
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Thursday, 14 December 2017
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Yun Kuen Cheung
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
Yun Kuen Cheung, 12/12/2017 09:10 PM
Last modified:
halma/MPII/DE, 01/31/2019 12:00 AM
  • Yun Kuen Cheung, 12/12/2017 09:15 PM
  • Yun Kuen Cheung, 12/12/2017 09:10 PM -- Created document.