Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
On multiaspect graphs
Wehmuth K., Fleury É., Ziviani A. Theoretical Computer Science651 (C):50-61,2016.Type:Article
Date Reviewed: Mar 1 2017

Many application domains require generalizations of the classical definition of directed graphs, for example, systems whose structures evolve over time (time-varying networks); systems that can be represented as conjunctions of interdependent networks (multilayer networks), for example, traffic networks with multiple modes of transportation; and systems that combine both features, for example, the service schedule of a public transportation network. For such applications, different graph generalizations have been introduced in a rather ad hoc manner.

This paper introduces the concept of a multiaspect graph (MAG) as a generic formalism that subsumes the previous formalisms as special cases. A MAG comprises a list of finite sets called “aspects” and a set of “edges” that are pairs of composite vertices; such a composite vertex is a tuple of elements of the various aspects. Each aspect can be, for example, a network layer, a time instant, a basic vertex, or any other independent feature. The authors elaborate the theory of MAGs, in particular the isomorphism between MAGS and directed graphs, from which the usual graph-theoretic notions can be lifted to MAGs.

The paper does not present deep mathematical results; the core intent is to make the abstraction accessible to a broader audience interested in modeling and analyzing complex networked systems. Thus, some general examples demonstrate the applicability of MAGs to modeling different kinds of networks. A companion paper discusses further details, such as MAG representations and algorithms; implementations of the algorithms are publicly available. The presented work may lead to further consolidation and unification of the field.

Reviewer:  Wolfgang Schreiner Review #: CR145092 (1705-0288)
Bookmark and Share
  Featured Reviewer  
 
Graph Algorithms (G.2.2 ... )
 
 
Complexity Measures And Classes (F.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Algorithms": Date
Planar graph decomposition and all pairs shortest paths
Frederickson G. (ed) Journal of the ACM 38(1): 162-204, 1991. Type: Article
Oct 1 1991
High probability parallel transitive-closure algorithms
Ullman J., Yannakakis M. SIAM Journal on Computing 20(1): 100-125, 1991. Type: Article
Dec 1 1991
Clique partitions, graph compression and speeding-up algorithms
Feder T., Motwani R.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1331991. Type: Proceedings
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy