abrodnik@watdragon.uwaterloo.ca (Andrej Brodnik (Andy)) (04/12/91)
Hi there! My friend from Ljubljana (Yugoslavia, SLovenia), asked me to post the following lines since he does not have an access to the newsgroup. He is asking for any references about the topic he is working on. Please respond him by e-mail directly, please. Regards Andrej --------------------------- HIS TEXT ----------------------------------- Given directed graph G and r-regular graph H (say, r = 4 or 6) a mapping of G into H is a function f which i) maps in 1-1 fashion each node of G into some node of H, and ii) maps each arc (u,v) of G into a path in H starting in f(u) and ending in f(v). The "area" of f(G) is the number of nodes of H which are involved in the mapping f(G), i.e., which belong to at least one path f((u,v)) for some arc (u,v) of G. I am interested in theory and algorithms for f(G) compression, i.e., minimizing the "area" of f(G). I am interested in any related problematics, especially with 6-regular target graphs H. Thanx in advance for any help Borut Robic