Abstract | ||
---|---|---|
Aiming at establishing a firm basic theory to ring-based information network management systems, our paper proposes a tie-set graph theory. We define a binary vector representing-a tie-set in a biconnected undirected graph G = ( V, E) as a tie-set vector. The set of tie-set vectors forms a vector space over the proposed law of composition, then a basis of the vector space, mu linear independent tie-set vectors, is defined as a tie-set basis. The essential key concept in our theory is a tie-set graph, which has a one-to-one correspondence to a tie-set basis and represents a relation between two tie-set vectors of the basis. Some important properties of tie-set graphs and their application to survivable mesh networks in modem high-speed backbone networks are also presented. Furthermore, as a general approach to network flow optimization problems, tie-set flow vector space is proposed based on the tie-set graph theory. A distributed algorithm for the network flow optimization problems and its application are also presented in this paper. Copyright (C) 2004 John Wiley Sons, Ltd. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1002/cta.275 | INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS |
Keywords | Field | DocType |
information network management, graph and network theory, tie-set graph | Line graph,Graph property,Cycle basis,Control theory,Directed graph,Algorithm,Theoretical computer science,Null graph,Random geometric graph,Connectivity,Graph (abstract data type),Mathematics | Journal |
Volume | Issue | ISSN |
32 | 6 | 0098-9886 |
Citations | PageRank | References |
16 | 1.98 | 5 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Toshio Koide | 1 | 351 | 17.06 |
Haruki Kubo | 2 | 16 | 2.32 |
Hitoshi Watanabe | 3 | 24 | 4.87 |