| dc.creator |
Fleischner, Herbert |
|
| dc.creator |
Mujuni, Egbert |
|
| dc.creator |
Paulusma, Daniël |
|
| dc.creator |
Szeider, Stefan |
|
| dc.date |
2016-09-21T12:38:29Z |
|
| dc.date |
2016-09-21T12:38:29Z |
|
| dc.date |
2009 |
|
| dc.date.accessioned |
2018-03-27T08:58:08Z |
|
| dc.date.available |
2018-03-27T08:58:08Z |
|
| dc.identifier |
Fleischner, H., Mujuni, E., Paulusma, D. and Szeider, S., 2009. Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21), pp.2045-2053. |
|
| dc.identifier |
http://hdl.handle.net/20.500.11810/3840 |
|
| dc.identifier |
10.1016/j.tcs.2008.12.059 |
|
| dc.identifier.uri |
http://hdl.handle.net/20.500.11810/3840 |
|
| dc.description |
Ful text can be accessed at
http://www.sciencedirect.com/science/article/pii/S0304397508009407 |
|
| dc.description |
We 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. |
|
| dc.language |
en |
|
| dc.publisher |
Elsevier |
|
| dc.subject |
Bicliques |
|
| dc.subject |
Parameterized complexity |
|
| dc.subject |
Covering and partitioning problems |
|
| dc.title |
Covering Graphs with Few Complete Bipartite Subgraphs |
|
| dc.type |
Journal Article, Peer Reviewed |
|