摘要:

AbstractWe consider a combinatorial problem arising in the design and operation of lightwave networks. Nodes in such networks are equipped with tunable transmitters and receivers and communication occurs when the frequency of some transmitter is the same as that of a receiver. This technology enables us to update the network topology to respond to changes in traffic patterns. There are two main optimization problems related to this network structure, one being the design of a target graph more suitable to (future) traffic conditions, and the other being the problem of transforming the current network to this target network. This paper discusses the second problem, i.e., the transition phase when the modifications on the current graph are made through a sequence of intermediate connection networks. In particular, we move from one graph to another by swapping two independent edges in the current graph for two other independent edges not in the current graph, so that the union forms a four‐cycle. We characterize the sequence requiring the minimum number of intermediate graphs together with the necessary and sufficient conditions for the existence of such a sequence. We also develop upper and lower bounds on the length of a shortest sequence by formulating an integer program and solving its continuous relaxation to optimality. We also give an efficient algorithm for the case when the intermediate graphs are required to be connected. © 1994 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230240402

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper, a schema of graphical parameters is proposed. Based on the parameter integrity introduced by Barefoot, Entringer, and Swart, members Ψ(G) of this schema have the general form Ψ(G) = min {|S| +Ψ(G ‐ S) :S Ψ V(G)}, whereΨ(G) is another given graphical parameter. Examples include integrity, mean integrity, connectivity, and vertex cover number. General results and bounds for the schema are derived. Also, properties that characterize such parameters are considered. © 1994 by John Wiley&So

ISSN:0028-3045    

DOI:10.1002/net.3230240403

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper, we present a heuristic for the Euclidean Steiner problem. The basis of this heuristic is to use the Delaunay triangulation to generate candidate Steiner vertices and then to remove redundant Steiner vertices via the minimal spanning tree. This basic algorithm is incorporated into a simulated annealing framework. Computational results are given for a number of test problems drawn from the literature. © 1994 by John Wiley&Sons, Inc

ISSN:0028-3045    

DOI:10.1002/net.3230240404

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

年代:1994

数据来源: WILEY

摘要:

AbstractInclusive connectivity parameters are measures of local connectivity that are natural restrictions of standard graph connectivity and edge connectivity. We examine the i‐connectivity analogs of super‐kand super‐λ graphs. The primary results here concern the graphsG+K2, i.e., the join of an arbitrary graph withK2. We show thatG+K2is super λ1‐connected for everyvϵV(G) and every edgeeϵE(G). Using these local results, we showG+Kn, n⩾ 2, is super λ‐connected. © 1994 by Joh

ISSN:0028-3045    

DOI:10.1002/net.3230240405

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

年代:1994

数据来源: WILEY

摘要:

AbstractGiven a graphG= (V, E), a subgraphS= (V, Es) is at‐spanner ofGif for every edgexy ϵ Ethe distance betweenxandyinSis at mostt. Spanners have applications in communication networks, distributed systems, parallel computation, and many other areas. This paper is concerned with the complexity of finding a minimum sizet‐spanner in a graph with bounded degree. A linear time algorithm is presented for finding a minimum‐size 2‐spanner in any graph whose maximum degree is at most four. The algorithm is based on a graph theoretical result concerning edge partition of a graph into a “triangle‐free component” and “triangular‐components.” On the other hand, it is shown that to determine whether a graph with maximum degree at most nine contains at‐spanner with at mostKedges (Kis given) is NP‐complete for any fixedt⩾ 2. © 1

ISSN:0028-3045    

DOI:10.1002/net.3230240406

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe consider the reliability of graphs for which nodes fail independently of each other with a constant probability 1 ‐p. The reliability of a graph is defined to be the probability that the induced subgraph of surviving nodes is connected. A graph is said to be uniformly best when, for all choices ofp, it is most reliable in the class of graphs with the same number of nodes and same number of edges. In this paper, we first extend the existing known set of uniformly best graphs. Next, we show that most classes of sparse graphs do not contain a uniformly best graph. Finally, we introduce the important notions of locally best and asymptotically best graphs and illustrate these concepts with a detailed study of graphs having the same number of nodes and edges. © 1994 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230240407

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

年代:1994

数据来源: WILEY

摘要:

AbstractThe best previous upper bound on the diameter of an edge domination critical graph with domination number γ is 3γ ‐ 5, found in a paper by Fulman. We improve the bound by one and exhibit a class of edge critical graphs with diameter [⅔γ ‐ 1]. © 1994 by John Wiley&

ISSN:0028-3045    

DOI:10.1002/net.3230240408

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

年代:1994

数据来源: WILEY

摘要:

AbstractConsider a network onn+ 1 vertices and twos‐t‐flowsfandf* of equal value.f* is called aflow spanneroffiff*(e) ⩽f(e) for every edgee. In this note, we prove that every integral flowfof valuen2‐ε (0 ⩽ ε ⩽ 2) has a flow spannerf* that uses at mostO(n2‐ε/2) many edges. A sequence of examples shows that this result is asymptotically optimal. © 1994 by Joh

ISSN:0028-3045    

DOI:10.1002/net.3230240409

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

年代:1994

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230240401

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

年代:1994

数据来源: WILEY