A study on the tie-set graph theory and network flow optimization problems

✍ Scribed by Toshio Koide; Haruki Kubo; Hitoshi Watanabe

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 198 KB
• Volume: 32
• Category: Article
• ISSN: 0098-9886
• DOI: 10.1002/cta.275

✦ Synopsis

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, μ 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 modern 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 © 2004 John Wiley & Sons, Ltd.