Research Goals

The goals of this work include:

1. Formal models:
   Define formal models for describing hierarchies inside graphs.
   There may be several different models which capture
   different subset of hierarchy characteristics.
   .

2. Recognition:
   Devise algorithms for quick separation of graphs where
   sizable hierarchies can be found from those graphs which
   are far from containing sizable hierarchies. Obviously,
   this includes defining "sizable" and "far from"
   in the context of graphical hierarchies. Different formal
   models may have different recognition algorithms.
   .

3. Decomposition:
   Devise algorithms for efficient decomposition of graphs containing
   hierarchies to hierarchy representations (HRDAGs) and possibly
   a residue which can not be hierarchically decomposed.
   Again, different formal models may have different decomposition algorithms.
   .

4. Empirical study:
   Find empirically which of these hierarchy types appear in graphs
   generated from engineering and natural source. Compare to random
   graphs to show that these hierarchies are not just a random phenomena.
   Definitions and algorithms of items 1,2 and 3 should be
   changed and adapted according to the empiric findings.

5. Graph-theoretic and logical properties
   .

6. Solving logical and numerical problems:
   on hierarchies with formal representation.
   Again, algorithms may differ between models.
   .

7. Non-exact hierarchies:
   Devise models and recognition algorithms for approximate
   hierarchies: where reused entities resemble each other
   but have some differences between them.
   .

8. Empirical study of non-exact hierarchies, i.e., hierarchies
   where modules are not instantiated in the same way every time,
   but where instances of a module may have only partial similarities
   between them.