Covering Graphs with Few Complete Bipartite Subgraphs

Simple item page
dc.contributor.authorFleischner, Herbert
dc.contributor.authorMujuni, Egbert
dc.contributor.authorPaulusma, Daniƫl
dc.contributor.authorSzeider, Stefan
dc.date.accessioned2016-09-21T12:38:29Z
dc.date.available2016-09-21T12:38:29Z
dc.date.issued2009
dc.descriptionFul text can be accessed at http://www.sciencedirect.com/science/article/pii/S0304397508009407en_US
dc.description.abstractWe consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the biclique partition problem is defined similarly with the additional condition that the bicliques are required to be mutually edge-disjoint. The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques, the biclique vertex-partition problem is defined similarly with the additional condition that the bicliques are required to be mutually vertex-disjoint. All these four problems are known to be NP-complete even if the given graph is bipartite. In this paper, we investigate them in the framework of parameterized complexity: do the problems become easier if k is assumed to be small? We show that, considering k as the parameter, the first two problems are fixed-parameter tractable, while the latter two problems are not fixed-parameter tractable unless P=NP.en_US
dc.identifier.citationFleischner, H., Mujuni, E., Paulusma, D. and Szeider, S., 2009. Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21), pp.2045-2053.en_US
dc.identifier.doi10.1016/j.tcs.2008.12.059
dc.identifier.urihttp://hdl.handle.net/20.500.11810/3840
dc.language.isoenen_US
dc.publisherElsevieren_US
dc.subjectBicliquesen_US
dc.subjectParameterized complexityen_US
dc.subjectCovering and partitioning problemsen_US
dc.titleCovering Graphs with Few Complete Bipartite Subgraphsen_US
dc.typeJournal Article, Peer Revieweden_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Covering graphs with few complete bipartite subgraphs.pdf
Size:
199.28 KB
Format:
Adobe Portable Document Format
Description:
Abstract
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Department of Mathematics