摘要:

AbstractThis article deals with the problem of minimizing the transmission delay in Illiac‐type interconnection networks for parallel or distributed architectures or in local area networks. A double‐loop network (also known as circulant)G(n,h), consists of a loop ofnvertices where each vertexiis also joined by chords to the verticesi±hmodn. An integern, a hoph, and a networkG(n,h)are called optimal if the diameter ofG(n,h)is equal to the lower boundkwhenn∈R[k] = {2k2− 2k+ 2, …,2k2+ 2k+ 1}. We determine new dense families of values ofnthat are optimal and such that the computation of the optimal hop is easy. These families cover almost all the elements ofR[k] ifkork+ 1 is prime and cover 92% of all values of

ISSN:0028-3045    

DOI:10.1002/net.3230210102

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

年代:1991

数据来源: WILEY

摘要:

AbstractIfkis a nonnegative integer andxis a vertex of a treeT, thek‐ball branch weight ofx, denotedb(x;k), is the number of vertices in a largest subtree ofT, all of whose vertices are a distance at leastk+ 1 fromx. Thek‐ball branch weight centroid ofT, denotedW(T;k), consists of all verticesxofTfor whichb(x;k)is a minimum. The usual branch weight centroid ofT(which is also the median) isW(T;0), and the center ofTisW(T;r), whereris the radius ofT. In this paper, the structure of the subgraph spanned byW(T;k)is examined. Similarities and differences with Slater'sk‐centrum [6] andk‐nucleus [7] are di

ISSN:0028-3045    

DOI:10.1002/net.3230210103

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

年代:1991

数据来源: WILEY

摘要:

AbstractIn this paper, we examine two related problems of inferring the evolutionary history ofnobjects, either from present characters of the objects or from several partial estimates of their evolutionary history. The first problem is called thePhylogenyproblem, and second is theTree Compatibilityproblem. Both of these problems are central in algorithmic approaches to the study of evolution and in other problems of historical reconstruction. In this paper, we show that both of these problems can be solved by graph theoretic methods in linear time, which is time optimal, and which is a significant improvement over existing methods.

ISSN:0028-3045    

DOI:10.1002/net.3230210104

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

年代:1991

数据来源: WILEY

摘要:

AbstractA newO(nm)label‐correcting algorithm is presented for finding shortest paths from a given node to all other nodes in a network ofnnodes andmarcs or finding a directed cycle of negative length. In this algorithm, a node is scanned on thek‐th scanning step only if its “label depth”—i.e., the length of the path corresponding to the distance label—equalsk. Variants of this algorithm are discussed, and computational results show that several of these are very efficient. A new criterion for detecting a negative cycle that is also based on the label depth of a node is given, and computational tests show that it is extremel

ISSN:0028-3045    

DOI:10.1002/net.3230210105

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

年代:1991

数据来源: WILEY

摘要:

AbstractGiven a graphG=(V,E)and a setN⊆V, we consider the problem of finding a minimum‐weight multiway cut that separates each pair of nodes inN. In this paper we give an integer programming formulation of this problem and study the associated polyhedron. We give some computational results to support the strength of our facets. We also give some efficiently solvable instan

ISSN:0028-3045    

DOI:10.1002/net.3230210106

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

年代:1991

数据来源: WILEY

摘要:

AbstractManufacturers often use digital waveforms to specify critical device timing. In this paper, we study two problems related to the use of such specifications. First, we are interested in verifying that the timing information is consistent to begin with. Second, given waveform specifications of two devices that are to be linked, we wish to know whether one satisfies the other's timing requirements. We construct a model of the timing information conveyed by the waveform convention and show how both problems can be solved efficiently with optimization techniques. To illustrate our arguments, we compare the write‐cycle timing of a typical CPU with that of a RAM devic

ISSN:0028-3045    

DOI:10.1002/net.3230210107

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

年代:1991

数据来源: WILEY

摘要:

AbstractIn this article, we consider an asymmetric market disequilibrium model in a spatial setting in the case of rigid prices and/or controls. In this problem, the markets need no longer clear. We show that the disequilibrium problem can be reformulated as an equilibrium problem over an abstract network with special structure. We then propose a network decomposition algorithm for the computation of the solution that exploits the structure and establishes convergence results using the theory of variational inequalities. Our computational results demonstrate the suitability of this approach for large‐scale market problem

ISSN:0028-3045    

DOI:10.1002/net.3230210108

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

年代:1991

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230210101

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

年代:1991

数据来源: WILEY