Partitioning multi-edge graphs |
| |
Authors: | Ravi Varadarajan |
| |
Affiliation: | (1) Computer and Information Sciences Department, University of Florida, 32611 Gainesville, FL, USA |
| |
Abstract: | We introduce a new kind of graph called multi-edge graph which arises in many applications such as finite state Markov chains and broadcasting communication networks. A cluster in such a graph is a set of nodes such that for any ordered pair of nodes, there is a path of multi-edges from one to the other such that these edges remain within the same set. We give two algorithms to partition a multi-edge graph into maximal clusters. Both these algorithms are based on the depth-first search algorithm to find strongly connected components of the directed graph. We also discuss some applications of clustering in multi-edge graphs. |
| |
Keywords: | F2.0 G2.2 |
本文献已被 SpringerLink 等数据库收录! |
|