摘要:

AbstractLetG(V, E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints to be a transmitter, the other to be a receiver, and sending a message from the transmitter to the receiver through the line. We define several different models for communication networks, all subject to the two following axioms: a vertex cannot act as a transmitter and as a receiver simultaneously and a vertex cannot receive through two lines simultaneously. In each of the models, two problems arise: What is the maximum number of lines one can test simultaneously? and What is the minimum number of phases necessary for testing the entire network?, where, by “phase” we mean a period in which some tests are conducted simultaneously. We show that in most models, including the “natural” model of radio communication, both problems are NP‐hard. In some models the problems can be solved by reducing them to either a maximum matching problem or an edge coloring problem for which polynomial algorithms are known. One model remains for which the complexity of the minimization problem i

ISSN:0028-3045    

DOI:10.1002/net.3230140102

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

年代:1984

数据来源: WILEY

摘要:

AbstractShortest and/or longest path analysis is a major analytical component of quantitative models used by transportation planners. The importance of shortest path analysis in all phases of transportation planning has given rise to intensive research and software development over the last three decades for solving shortest path problems. This paper presents a new hybrid solution algorithm called THRESH, which integrates the features of label setting and label correcting algorithms, yet appears to have performance characteristics that transcend both. Preliminary computational results indicate that it is substantially more efficient than the methods determined to be best by previous studies.

ISSN:0028-3045    

DOI:10.1002/net.3230140103

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

年代:1984

数据来源: WILEY

摘要:

AbstractThe scheduling and planning of a project can be represented by two types of networks, namely, by the activity networks and the event networks. For each project, there exists a unique activity network without redundant (transitive) arcs but since there is an infinite number of different‐sized event networks, the problem is to find an event network with the minimum number of dummy activities. Krishnamoorthy and Deo proved that this problem is NP‐complete. In Sections III and IV we characterize those activity networks which have event networks without dummy activities and present a polynomial‐time algorithm which tests if a given activity network requires dummy activities in the event network. The same result is also proved for a generalization of the real‐world problem to arbitrary digraphs. Finally, we present an example which shows that the number of nodes and the number of arcs in event networks cannot be minimized simulta

ISSN:0028-3045    

DOI:10.1002/net.3230140104

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

年代:1984

数据来源: WILEY

摘要:

AbstractThe number of vertex cut sets of sizekin a graph of connectivitykhas been used as a measure of network reliability. LetGbe a regular graph withNvertices, valencyk, connectivityk, and with the minimum number of vertex cut sets withkvertices. The problem of constructing such a graphGfor each pair (N, k) is known to be difficult. We show how to construct infinite families of such graphs in various cases. These cases are spread through the range 3/8 ≤k/N<1. We also deal with cases in whichkis small and cases withN ‐ ksm

ISSN:0028-3045    

DOI:10.1002/net.3230140105

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

年代:1984

数据来源: WILEY

摘要:

AbstractTwo fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph withnvertices in which there areknode‐disjoint paths between any two nodes. The generated graphs will have a minimum number of edges and a diameter which is twice as large as the theoretical minimum. The algorithm is useful for the construction of large networks because it has a time complexity ofO(n2

ISSN:0028-3045    

DOI:10.1002/net.3230140106

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

年代:1984

数据来源: WILEY

摘要:

AbstractIn this paper, we study a special single‐commodity spatial equilibrium problem. We show how the problem is related to a shortest‐path problem and develop a simple algorithm for its solution. We also discuss an extension of the single‐commodity problem to a multicommodity pr

ISSN:0028-3045    

DOI:10.1002/net.3230140107

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

年代:1984

数据来源: WILEY

摘要:

AbstractThe problem is to be able to respond to inquiries of the form “Are verticesuandvof graphGconnected?” as quickly as possible in an on‐line situation where edges are being inserted into and deleted from the graph. Recently Even and Shiloach presented a data structure and algorithm involving three synchronized processes to handle the deletion case. An alternative algorithm, LEVELS, is presented to update their data structure. This algorithm is more efficient than theirs and has the further feature of not requiring synchronized processes, so that it is much easier to implement. Finally the LEVELS algorithm is compared to and contrasted with an algorithm using a spanning‐forest data structure for both edge insertion and deletion. The LEVELS algorithm appears to be better for deletion, while the spanning‐forest algorithm is better for

ISSN:0028-3045    

DOI:10.1002/net.3230140108

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

年代:1984

数据来源: WILEY

摘要:

AbstractLetG= (V, E) be a graph with weight functionw:Erightarrow Z+and length functionl:E/rightarrow Z+. The problem of determining for v1, V2/inVwhether there is a path from v1to v2with weight at mostWand length at mostLis NP‐complete. This paper gives two approaches to meeting or approximating the length and weight constraints. The first approach is to use a pseudopolynomial‐time algorithm which determines whether a path meets the constraints. Its running time isO(n5blognb) wheren= |V| andbis the largest length or weight. If tables withO(n3b) entries are kept thenallinstances of multiple constraints may be decided. Table size may be substantially decreased if one is willing to tolerate incorrect answers to rare instances. The algorithm is suitable for distributed execution. In the second approach, an objective function is defined which evaluates a path's distance from meeting the constraints. Polynomial‐time algorithms attempt to find good paths in terms of the objective function. One algorithm is at most 1.62 times worst than optimal. A notion of “average worst‐case behavior” is defined. The algorithm's “average” behavior is 1.51 times wor

ISSN:0028-3045    

DOI:10.1002/net.3230140109

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

年代:1984

数据来源: WILEY

摘要:

AbstractThe conventional network flow model is generalized by replacing the capacity constraints on the flow of each arc by a constraint that the set of flows lies in a compact set; the resulting model is called the compact flow network model. A necessary condition for the maximal compact flow is presented. The max‐flow‐min‐cut theorem is generalized to compact flow networks. The condition that is required for the maximal flow to be equal to the minimal cut is examined. The max‐flow‐min‐cut theorem is used to derive a necessary and sufficient condition for feasibility of the multiterminal supply‐demand problem based on the compact flow model. As an application, the electric power supply‐demand problem is discussed from the compact flo

ISSN:0028-3045    

DOI:10.1002/net.3230140110

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

年代:1984

数据来源: WILEY

摘要:

AbstractBoesch, Harary, and Kabell recently introduced two measures of network vulnerability. They defined the persistence (edge persistence) of a graph as the minimum number of vertices (edges) whose deletion increases the diameter. In their paper they posed questions relating the existence of graphs with a prescribed number of edges, number of vertices, diameter, and persistence (edge persistence). In this paper we consider this extremal problem.

ISSN:0028-3045    

DOI:10.1002/net.3230140111

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

年代:1984

数据来源: WILEY