Technical Report CS-2011-12

TR#:CS-2011-12
Class:CS
Title: Algorithms on 2-Acyclic-Subtree Filament Graphs
Authors: Fanica Gavril
PDFCS-2011-12.pdf
Abstract: Two intersecting subtrees of a graph D are 2-acyclic if and only if their intersection is a subtree. Let GI(V,F) be the intersection graph of a family of 2-acyclic subtrees of a graph D. In the present paper we define intersection graphs of 2-acyclic-subtree filaments on any graph D; the subtree filaments are similarly defined as the subtree filaments based on subtrees of a tree. We describe polynomial time algorithms for various problems on 2-acyclic-subtree filament graphs G when their base graphs GI have algorithms for related problems. The problems are to find maximum induced complete bipartite subgraphs, maximum weight holes of a given parity, minimum dominating holes, maximum weight antiholes and some others.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2011/CS/CS-2011-12), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2011
To the main CS technical reports page

Computer science department, Technion
edit