摘要:

AbstractA bounded generalized processing network model has the structure of a cost‐minimizing generalized network, with additional side constraints that, for flows on some arcs, place upper and lower bounds that are proportional to flows on other arcs. We propose and test a heuristic algorithm that takes advantage of the near‐network structure by solving a sequence of generalized network LPs whose data are adjusted in a manner suggested by the solution at previous steps. The algorithm extends an earlier algorithm to achieve better solutions, at the cost of more computing effort. In tests, the algorithm is much faster than is application of the general purpose linear programming code MINOS, and the speed advantage increases with problem size: The algorithm is 27 times faster than MINOS on the largest test problem. The algorithm almost always obtains solutions within 0.05% of the optimum. The proportionality constraints are relaxed in the algorithm, yet the solutions to the test problems satisfy the proportionality constraints to within, at worst, 0.25% of the given proportionality limits. © 1994 John Wiley&Sons,

ISSN:0028-3045    

DOI:10.1002/net.3230240202

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

年代:1994

数据来源: WILEY

摘要:

AbstractGiven a graphG = (V, E), the graph planarization problem is to find a largest subsetFofE, such thatH= (V, F) is planar. It is known to be NP‐complete. This problem is of interest in automatic graph drawing, in facilities layout, and in the design of printed circuit boards and integrated circuits. We present a two‐phase heuristic for solving the planarization problem. The first phase devises a clever ordering of the vertices of the graph on a single line and the second phase tries to find the maximal number of nonintersecting edges that can be drawn above or below this line. Extensive empirical results show that this heuristic outperforms its competitors. © 1994 by John Wiley&Sons,

ISSN:0028-3045    

DOI:10.1002/net.3230240203

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

年代:1994

数据来源: WILEY

摘要:

AbstractFor a given connected graphGof ordern, a routingRis a set ofn(n‐ 1) simple pathsR(x, y) specified for every ordered pair (x, y) of vertices inG. A routingRis consistent if for every vertexzonR(x, y) the pathsR(x, z) andR(z, y) are induced byR(x, y). A network is defined by an ordered pair (G, R), whereGis a connected graph andRis a routing ofG. The vertex‐forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths ofRpassing through any vertex ofG. The minimum of ζ(G, R) over all possible routings of a connected graphGis denoted by ζ(G). Similarly, the notion of the edge‐forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex‐forwarding index cannot be obtained by taking the minimum of ζ(G, R) over all possible consistent routings ofG. However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ(G) is NP‐complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge‐forwarding index. © 1994 Joh

ISSN:0028-3045    

DOI:10.1002/net.3230240204

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

年代:1994

数据来源: WILEY

摘要:

AbstractAtotal dominating function(TDF) of a graphG= (V, E) is a functionf:V→ [0, 1] such that for each ν ϵV, ΣuϵN(v)f(u) ⩾ 1 [whereN(v)denotes the open neighborhood of vertexv]. Integer‐valued TDFs are precisely characteristic functions of total dominating sets ofG. Convex combinations of two TDFs are themselves TDFs but convex combinations of minimal TDFs (MTDFs) are not necessarily minimal. This paper is concerned with the existence of auniversalMTDF in a graph, i.e., a MTDFgsuch that convex combinations ofgand any other MTDF are themselves minimal. © 1994 by John Wiley

ISSN:0028-3045    

DOI:10.1002/net.3230240205

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe present an algorithm that does packet routing on anN‐node butterfly in timeO(logN) with small constants. The algorithm is based on Ranade's probabilistic PRAM emulation. We simplify the algorithm by focusing on packet routing and prove bounds on its performance for the cases of permutation routing and uniform, random traffic. The main results are upper bounds on the probability that the routing time exceedstfor a fixed queue size. The simplifications made to Ranade's original algorithm and a more careful analysis enabled us to achieve better constants, which, to the best of our knowledge, are the best to date. © 1994 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230240206

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

年代:1994

数据来源: WILEY

摘要:

AbstractWe propose a new routing strategy for the KYKLOS II multiprocessor interconnection network that achieves minimum distance for the path between any two processors. For KYKLOS II with 2nprocessors, the average distance is shorter than those of previous routing strategies by approximately 2 log2n. The traffic density, a measure of traffic concentration, is better than previous strategies for up to 2000 processors, though asymptotically inferior to a strategy proposed by Jenevein and Menezes. © 1994 by John Wiley&Sons, Inc

ISSN:0028-3045    

DOI:10.1002/net.3230240207

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

年代:1994

数据来源: WILEY

摘要:

AbstractIn this paper, we present a polynomial algorithm that finds an edge‐maximal triangulated subgraph of an arbitrary graph. Then, we use this algorithm as a heuristic for the maximum (weight) clique problem. Finally, a local search routine is incorporated into our heuristic. Computational results comparing our algorithm with two existing edge‐maximal triangulated subgraph algorithms in the literature show that the subgraphs found by our algorithm tend to contain more edges as well as a better clique of the original graph. Computational results comparing our heuristic with other heuristics, including an efficient randomized heuristic, also show the promise of our heuristic. © 1994 by John Wiley&Sons,

ISSN:0028-3045    

DOI:10.1002/net.3230240208

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

年代:1994

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230240210

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

年代:1994

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230240211

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

年代:1994

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230240212

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

年代:1994

数据来源: WILEY