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.


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.

Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
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