Browse Prior Art Database

Technique for Graph Coloring with Applications to Explicit Route Numbering in SNA Networks

IP.com Disclosure Number: IPCOM000049474D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Brenner, N: AUTHOR [+3]

Abstract

Current implementations of system network architecture (SNA) require the assignment of explicit route numbers (from 0 to 7) to each physical route in the network. The architecture contains rules defining those circumstances under which a given pair of routes must be assigned different explicit route numbers. The algorithm presently used to perform this assignment orders the physical routes and assigns the minimal number to each route sequentially, based on a bin-packing strategy. This technique often fails to successfully number all desired routes in large networks; failure to do so is sometimes given as evidence of a phenomenon called Explicit Route Number Explosion (ERN).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Technique for Graph Coloring with Applications to Explicit Route Numbering in SNA Networks

Current implementations of system network architecture (SNA) require the assignment of explicit route numbers (from 0 to 7) to each physical route in the network. The architecture contains rules defining those circumstances under which a given pair of routes must be assigned different explicit route numbers. The algorithm presently used to perform this assignment orders the physical routes and assigns the minimal number to each route sequentially, based on a bin-packing strategy. This technique often fails to successfully number all desired routes in large networks; failure to do so is sometimes given as evidence of a phenomenon called Explicit Route Number Explosion (ERN).

It has been observed that the route-numbering problem is isomorphic to coloring a graph such that adjacent nodes in the graph have different colors. Although the graph coloring problem has been shown to be a very hard one to solve optimally, heuristics exist which give good results. A new coloring algorithm is proposed which not only gives better results than those attained by the current route-numbering technique, but also performs favorably when compared with other graph coloring algorithms.

Define: the valency of a node as the number of nodes adjacent to it, the merger of a pair of non-adjacent nodes as the replacement in the graph of that pair and the edges which are incident to either of them by a single node and a set of edges which connect the new node to each node in the graph which was adjacent to at least one node of the pair. (The new node is called a descendant of each node of the pair and of any node of which either node of the paid is a descendant).

The new algorithm proceeds as follows to color the graph G:
1. While there is...