# On the Weighted Minimal Deletion of Rooted Bipartite Minors

Gassner, Elisabeth and Percan, Merijam
(2006)
*On the Weighted Minimal Deletion of Rooted Bipartite Minors.*

Technical Report
, 35 p.

## Abstract

We investigate the problem of finding a minimal weighted set of edges whose removal results in a graph without minors that are contractible onto a prespecified set of vertices. Such minors are called rooted. The problem of a minimal weighted deletion of all rooted K(i,3)-minors for a fixed integer i is proved to be NP-hard on general graphs. Furthermore, a polynomial time algorithm is developed for the rooted K(1,3)-minor deletion problem on planar graphs while for the rooted K(2,3)-free minor planar graphs a characterization is presented.

Actions:

Full text not available from this repository.
(Request a copy)

Editorial actions: |
View Item (Login required) |
---|

Content information:

Deposit Information:

ZAIK Number: | zaik2007-542 |
---|---|

Depositing User: | Merijam Percan |

Date Deposited: | 04 Jun 2007 00:00 |

Last Modified: | 11 Aug 2011 15:37 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/542 |