摘要:

AbstractLet A be a finite set of points in a Euclidean space Erand M a minimum spanning tree (MST) for A, regarded as a subset of Er. If A′ ⊂ Eris a finite subset of M, then M is a spanning tree for A ∪ A′, but in general M will no longer be an MST. However, if A′ is chosen to be the set of all the midpoints of the line segments of M, then M will be an MST for A ∪ A′. Examples are given in which at least |A| ‐ 1 points must be adjoined to avoid des

ISSN:0028-3045    

DOI:10.1002/net.3230080302

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

年代:1978

数据来源: WILEY

摘要:

AbstractA graph G is called hypohamiltonian if G is not hamiltonian but every vertex‐deleted subgraph G‐v is hamiltonian. The existence of a p‐vertex hypohamiltonian graph is open only for p = 14,17, and the existence of a p‐vertex, cubic hypohamiltonian graph is open only for p = 14,16,24,32. With the aid of a computer we have established that there is no hypohamiltonian graph of order 14, and no cubic hypohamiltonian graph of order 14 or 16. In addition, there is no hypohamiltonian graph of order 17 with girth ≥ 5. On the other hand, new p‐vertex, cubic hypohamiltonian graphs have been found fo

ISSN:0028-3045    

DOI:10.1002/net.3230080303

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

年代:1978

数据来源: WILEY

摘要:

AbstractGiven a connected graph with edge costs, we seek a spanning tree having a specified degree at one vertex r, with cost as small as possible. A previous algorithm, using edge exchanges, has run time 0(V2); we improve this to 0(E log log V+V log V). Here V and E are the number of vertices and edges. The algorithm uses edge exchanges ordered efficiently on a reduced graph; it also uses efficient algorithms for minimum spanning trees and priority queues.

ISSN:0028-3045    

DOI:10.1002/net.3230080304

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

年代:1978

数据来源: WILEY

摘要:

AbstractRamsey problems are examined for the different varieties of graphs and digraphs, with and without loops and multiple edges, and even for networks. In every case, the resulting Ramsey number either fails to exist, or has a trivial value, or equals the value for the underlying graph or digraph. Thus it appears there are no new interesting Ramsey numbers for multigraphs and networks.

ISSN:0028-3045    

DOI:10.1002/net.3230080305

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

年代:1978

数据来源: WILEY

摘要:

AbstractWe examine the complexity of a classical problem related to the design of centralized computer networks. Under very broad assumptions the problem is shown to be NP‐complete, and hence most probably intractable. The same result holds for the “Euclidean” case of the problem; however, in the latter case a simple algorithm produces solutions with relative error almost certainly arbitrarily close to

ISSN:0028-3045    

DOI:10.1002/net.3230080306

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

年代:1978

数据来源: WILEY

摘要:

AbstractConsider a directed, source‐sink network whose arcs either function or fail with known probabilities. This paper presents a decomposition algorithm for the exact computation of the reliability of such a network; that is, the probability that there exists a path from the network's source to its sink, consisting only of functioning arcs. The decomposition algorithm, which can be used even after the network can undergo no further modular decomposition, is based on a partitioning of the nodes of the network into subsets that can be sequentially analyzed. The algorithm permits arbitrary dependence among arcs that terminate at nodes belonging to the same subset of the partition but requires two arcs terminating at nodes belonging to different subsets to be independent. Computational experience from a computer implementation of the algorithm is also reporte

ISSN:0028-3045    

DOI:10.1002/net.3230080307

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

年代:1978

数据来源: WILEY

摘要:

AbstractThe problems of layout of printed circuits and large scale integrated chips are very complex and are therefore usually approached by heuristic methods.This paper presents a more analytic approach to an elementary subset of these problems, using combinatorial and graphtheoretic arguments.

ISSN:0028-3045    

DOI:10.1002/net.3230080308

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

年代:1978

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230080301

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

年代:1978

数据来源: WILEY