harrison@ENUXHA.EAS.ASU.EDU (John V. Harrison) (02/20/91)
Greetings to all great scholars, near and far!!!!! Please take a moment to consider the following (simple?) problem. Given: Consider a directed graph and its transitive closure. Let the graph be represented by a boolean adjacency (incidence) matrix A. Let the transitive closure be represented be a boolean (reachability) matrix TC. (Simple?) Problem: How can TC be updated (without completely recomputing TC) when an edge of the graph is deleted (i.e. an element in A is set to 0)? Is there a better representation than a matrix for the dynamic graph and its transitive closure that can support the fast update of the transitive closure when an edge is deleted (or perhaps require less space)? Surely this problem has been encountered! I would appreciate it if someone could suggest a solution or point me towards some relevant literature. Thanks, John --------------------------------------------------------------------------- John Harrison harrison@enuxha.eas.asu.edu Department of Computer Science Arizona State University Tempe, AZ 85287