摘要:

AbstractControl of a network, especially as it expands into new geographic areas, is one of the most important factors in assuring that both the reliability and availability of that network will not be adversely effected.When the General Electric Company first offered a commercial network as part of its Time‐Sharing service, only a small part of communications control was automated. The remainder of the control functions were performed manually. As the network grew from its infancy into what it is today, it could have become “An Operational Nightmare”.It became evident that it was necessary to develop into the network a completely automatic control system that would provide operations personnel with the tools for both recognizing and recovering from problems that might compromise either its availability or reliability. Included in this capability are the following:1The ability to detect and display the status of all the nodes.2The ability to detect and display the status of all links.3The ability to introduce new software.4The ability to measure the overall network performance.5The ability to schedule preventive maintenance.6The ability to detect imminent failures.This paper will show why this automated control system is necessary, how it is structured to record the pulse and heart‐beat of the network and finally how it is used to maintain the stability of the

ISSN:0028-3045    

DOI:10.1002/net.3230040402

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY

摘要:

AbstractAn analysis is made of the computational complexity of a class of heuristic algorithms for the solution of the minimal spanning tree problem subject to a restriction on the maximum number (or weight) of nodes in any subtree rooted at a distinguished node. This is of particular interest in designing networks with branch capacity restrictions. The algorithm is a modification of Kruskal's Algorithm where weights are assigned to the nodes and then used, along with the arc lengths, to select the order in which arcs are considered for inclusion in the spanning tree. Considerations in the efficient implementation of such algorithms are examined and several heuristics for assigning node weights are compared.

ISSN:0028-3045    

DOI:10.1002/net.3230040403

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY

摘要:

AbstractThe concept of an alternating path has been very useful in analyzing matching problems and has formed the basis for a number of matching algorithms. However, no techniques have been devised to find the shortest alternating path in a weighted graph. This paper defines different types of directed and undirected alternating paths, and shows how the problem of finding the shortest directed alternating path can be transformed into a problem of finding the shortest path in a directed graph. Utilizing this transformation, an efficient algorithm is developed for finding the shortest undirected alternating path. Computational experience is given. Extensions of the techniques in this paper to other types of alternating paths are discussed.

ISSN:0028-3045    

DOI:10.1002/net.3230040404

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230040405

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY

摘要:

AbstractA nonlinear programming algorithm is applied to multicommodity flow problems with nonlinear costs. The algorithm can handle a wide class of problems and unifies several seemingly diverse approaches previously published. Significant computational simplifications that occur under special conditions are discussed.

ISSN:0028-3045    

DOI:10.1002/net.3230040406

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY

摘要:

AbstractConsider a finite family of non‐empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of arcs on a circularly ordered set is called a circular‐arc graph. In this paper we give a characterization of the circular‐arc graph and we describe efficient algorithms for recognizing two subclasses. Also, we describe efficient algorithms for finding a maximum independent set, a minimum covering by cliques and a maximum clique of a circular‐ar

ISSN:0028-3045    

DOI:10.1002/net.3230040407

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY

摘要:

AbstractA clique of a graph is a maximal complete subgraph. A (p,q)‐graph has p points and q lines. A clique‐extremal (p,q)‐graph has either the maximum or the minimum number of cliques among all (p,q)‐graphs. Moon and Moser have determined constructively the maximum number of cliques in a p‐point graph. The problem of studying the clique‐extremal (p,q)‐graphs is now investigated. We first develop a standard form for such extremal graphs. These standard forms are shown to have a complementary kind of analogy with respect to maximu

ISSN:0028-3045    

DOI:10.1002/net.3230040408

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230040401

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1974

数据来源: WILEY