Technical Report CS-2006-16

Title: Intersection Representations of Matrices by Subtrees and Unicycles on Graphs
Authors: Fanica Gavril, Ron Pinter and Shmuel Zaks
Abstract: Consider a 0-1 matrix M(i,j) with columns C={c1, c2,…, cm}, and rows R, or – equivalently – a hypergraph M(R,C) having M as its adjacency matrix (where R are the vertices and C are the hyperedges). Denote ri={cj| cj in C and M(i,j)=1}. We consider the following two problems: (a) Is there a graph H, with vertex set C, such that every vertex subgraph H(ri) of H is a tree and the intersection of every two such trees is also a tree? (b) Is there a graph H, with vertex set C, such that every H(ri) is a unicycle and the intersection of every two and every three unicycles is a tree? These questions occur in application areas such as database management systems and computational biology; e.g., in the latter they arise in the context of the analysis of biological networks, primarily for the purpose of data clustering. We describe algorithms to find such intersection representations of a matrix M (and equivalently of the hypergraph M), when they exist. SUBMITTED: September 2006.
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 files directly. The latter URLs may change without notice.

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

Computer science department, Technion