Technical Report CS-2007-03

Title: Algorithms on interval filament graphs
Authors: Fanica Gavril
Abstract: We describe polynomial time algorithms to find holes and antiholes of a given parity, and minimum dominating holes, in interval filament graphs, circular-arc filament graphs and subtree filament graphs, implying polynomial time algorithms to test for perfectness. Also, we describe polynomial time algorithms to find minimum coverings by cliques for their subfamilies of perfect graphs. The class of interval filament graphs, introduced by Gavril, contains the classes of cocomparability, polygon-circle and chordal graphs.
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 (, 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 2007
To the main CS technical reports page

Computer science department, Technion