bluuebunny/crossref_metadata_2025_split huggingface dataset:
Locating an obnoxious facility on a euclidean network to minimize neighborhood damage
Authors: Sung Chang Sup , Joo Cheol Min 
Published: May 2007

AbstractThis paper considers the problem of locating an obnoxious facility on a Euclidean network that could inflict damage within a λ distance of its location point. The objective is to find a location point that minimizes the sum of weights within the circle of radius λ centered at the location point, where each weight (assigned to a point on the network) represents a numerical scale that typically signifies the extent of the undesirability (or the damage cost) due to the facility located near the weighted point. The weights are assumed discretely distributed over all the nodes but uniformly distributed on all the links of the network. In the problem analysis, some optimal solution properties are found, e.g., the objective function is lower semicontinuous piecewise concave and there is at least one optimal location point in a finite set of candidate points. Using these properties, an efficient solution algorithm is derived and tested with several numerical problems. © 1994 by John Wiley & Sons, Inc.
Weighted k‐cardinality trees: Complexity and polyhedral structure
Authors: Fischetti Matteo , Hamacher Horst W. , Jørnsten Kurt , Maffioli Francesco 
Published: May 2007

AbstractWe consider the k‐CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil‐field leasing and facility layout. Although the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k‐CARD TREE and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex hull of the integer solutions is studied. © 1994 by John Wiley & Sons, Inc.
A new characterization of tree medians with applications to distributed sorting
Authors: Gerstel O. , Zaks S. 
Published: May 2007

AbstractA new characterization of tree medians is presented: We show that a vertex m is a median of a tree T with n vertices iff there exists a partition of the vertex set into [n/2] disjoint pairs (excluding m when n is odd), such that all the paths connecting the two vertices in any of the pairs pass through m. We show that in this case the sum of the distances between these pairs of vertices is the largest possible among all such partitions, and we use this fact to discuss lower bounds on the message complexity of the distributed sorting problem. We show that, given a network of a tree topology, choosing a median and then routing all the information through it is the best possible strategy, in terms of worst‐case number of messages sent during any execution of any distributed sorting algorithm. We also discuss the implications for networks of a general topology and for the distributed ranking problem. © 1994 by John Wiley & Sons, Inc.
Use of continuous approximations within discrete algorithms for routing vehicles: Experimental results and interpretation
Authors: Hall Randolph W. , Du Yafeng , Lin Julia 
Published: May 2007

AbstractThis paper creates and tests a vehicle routing heuristic that combines features of continuous space modeling and discrete modeling. The goals of the paper were (1) to determine whether exploiting continuous space approximations in the formation of an initial partition of customers into districts produces significant improvements in solution quality and (2) to test the validity of Daganzo's route‐length approximation in cases where shipment sizes are either identical or variable. The initial partition is created by dividing the service region into multiple annuli and then partitioning the annuli with a modified sweep algorithm. The initial solution is iteratively updated with a generalized assignment algorithm, which employs a new method for approximating the cost of inserting a stop into a tour. Computational tests have been systematically performed on over 500 sample problems with up to 170 stops and 70 districts. Unlike prior research, sample problems are sufficiently large to exhibit the multiple‐annuli phenomenon studied in Daganzo's work. Results show that continuous space models can provide substantial improvements in the initial customer partition compared to single‐annulus methods. However, after repeated application of a generalized assignment algorithm, the initial advantage of the continuous space solution tends to evaporate. Results also show that Daganzo's model provides accurate predictions of average distance between stops, especially on large problems with identical shipment sizes. © 1994 by John Wiley & Sons, Inc.
A fast algorithm for bounded generalized processing networks
Authors: Fuller J. David , Lan B. 
Published: May 2007

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, Inc.
An efficient graph planarization two‐phase heuristic
Authors: Goldschmidt Olivier , Takvorian Alexan 
Published: May 2007

AbstractGiven a graph G = (V, E), the graph planarization problem is to find a largest subset F of E, such that H = (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, Inc.
Forwarding indices of consistent routings and their complexity
Authors: Heydemann M. C. , Meyer J. C. , Sotteau D. , Opatrny J. 
Published: May 2007

AbstractFor a given connected graph G of order n, a routing R is a set of n(n ‐ 1) simple paths R(x, y) specified for every ordered pair (x, y) of vertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex‐forwarding index ζ(G, R) of a network (G, R) is the maximum number of paths of R passing through any vertex of G. The minimum of ζ(G, R) over all possible routings of a connected graph G is 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 of G. 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 John Wiley & Sons, Inc.
Sharper analysis of packet routing on a butterfly
Authors: Krishna Arvind , Hajek Bruce , Pietracaprina Andrea 
Published: May 2007

AbstractWe present an algorithm that does packet routing on an N‐node butterfly in time O(log N) 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 exceeds t for 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, Inc.
Minimal‐distance routing for KYKLOS II
Authors: Du Ding‐Zhu , Hwang F. K. , Odlyzko A. M. , Zhang Yanjung 
Published: May 2007

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 2n processors, 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.
Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
Authors: Xue Jue 
Published: May 2007

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, Inc.
Local bipartite turán graphs and graph partitioning
Authors: Lee Jon , Ryan Jennifer 
Published: May 2007

AbstractMotivated by the NP‐hard problem of finding a minimum‐weight balanced bipartition of an edge‐weighted complete graph, we studied the class of graphs having the same degrees as bipartite Turán graphs. In particular, we established a maximal set of linear equations satisfied by the counts of the possible incidences of 3‐ and 4‐cycles on such graphs. This leads to extremal results that we exploit in a heuristic for the partitioning problem, as well as in the computation of a Lagrangian bound. Preliminary computational results with the heuristic appear to be quite promising. Further results are established linking various adjacency concepts and measures of nonbipartiteness for such graphs. We also demonstrate the potential power of the Lagrangian bound via a family of examples. © 1994 by John Wiley & Sons, Inc.
Stochastic programs over trees with random arc capacities
Authors: Powell Warren B. , Cheung Raymond K. 
Published: May 2007

AbstractIn this paper, we study a special class of stochastic programs where the recourse problem consists of trees with random arc capacities, which we call tree recourse. We develop an efficient procedure to obtain the expected recourse function exactly for single‐stage problems. This procedure is used in a backward recursion to find the exact expected recourse function for multistage trees. We show that for large trees n‐stage networks can be solved more easily than can a single‐stage network with n‐levels. We also show that the expected recourse functions for single‐stage and n‐stage formulations of the same network can be quite similar. Finally, we illustrate the potential of using the tree recourse problems in a more general stochastic network problem. © 1994 by John Wiley & Sons, Inc.
Mengerian properties, hamiltonicity, and claw‐free graphs
Authors: Flandrin E. , Li H. 
Published: May 2007

AbstractIn relation to the Property Pd,m, we define two parameters generalizing the diameter and the independence number of a graph, study their behaviors, and find new conditions depending on those parameters for a claw‐free graph to be Hamiltonian. © 1994 by John Wiley & Sons, Inc.
A degree sequence problem related to network design
Authors: Bienstock Daniel , Günlük Oktay 
Published: May 2007

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, Inc.
A delaunay triangulation‐based heuristic for the euclidean steiner problem
Authors: Beasley J. E. , Goffinet F. 
Published: May 2007

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.
On super i‐connected graphs
Authors: Boland James W. , Ringeisen Richard D. 
Published: May 2007

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‐k and super‐λ graphs. The primary results here concern the graphs G + K2, i.e., the join of an arbitrary graph with K2. We show that G + K2 is super λ1‐connected for every v ϵ V(G) and every edge e ϵ E(G). Using these local results, we show G + Kn, n ⩾ 2, is super λ‐connected. © 1994 by John Wiley & Sons, Inc.
Note: The diameter of edge domination critical graphs
Authors: Paris Matteo 
Published: May 2007

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 & Sons, Inc.
Note: Small integral flows need only sparse networks
Authors: Althöfer Ingo 
Published: May 2007

AbstractConsider a network on n + 1 vertices and two s ‐ t‐flows f and f * of equal value. f * is called a flow spanner of f if f *(e) ⩽ f(e) for every edge e. In this note, we prove that every integral flow f of value n2‐ε (0 ⩽ ε ⩽ 2) has a flow spanner f * that uses at most O(n2‐ε/2) many edges. A sequence of examples shows that this result is asymptotically optimal. © 1994 by John Wiley & Sons, Inc.
A bad submatrix is easy to find
Authors: Swaminathan R. P. 
Published: May 2007

AbstractA {0, 1}‐matrix is a consecutive 1's matrix, abbreviated C1M, if there exists a path P such that the vertices of P are indexed on the rows of M and the columns of M are the incidence vectors of the vertex‐sets of subpaths of P. In this paper, given a “special” r × c non‐C1M having n 1's, an O(r + c + n) time algorithm is presented to find a “minimal” submatrix that is also a non‐C1M. The motivation for finding such a “bad” submatrix comes from generating suitable cuts while solving traveling salesman problems using a cuttingplane method. © 1994 by John Wiley & Sons, Inc.
Computation of the forwarding index via flows: A note
Authors: de le Vega W. Fernandez , Manoussakis Y. 
Published: May 2007

AbstractIn a given network with n vertices, a routing is defined as a set of n(n − 1) routes, one route connecting each ordered pair of vertices. The load of a vertex is the number of routes going through it. The forwarding index of the network is the minimum of the largest load taken over all routings. We show that the problem of determining the value of the forwarding index (respectively, the forwarding index of shortest routings) is an instance of the multicommodity flow problem (respectively, flow with multipliers). Since many very good heuristics or approximation algorithms are known for these flow problems, it follows from our results that all of these methods can be used for calculating the forwarding index. © 1994 by John Wiley & Sons, Inc.
A proof of Boesch's conjecture
Authors: Wang Guifang 
Published: May 2007

AbstractA well‐known model for network reliability studies consists of an undirected graph with perfectly reliable nodes and equal and independent edge failure probabilities. The measure of reliability is defined to be the probability that a graph is connected. A well‐defined synthesis problem is to find a graph that maximizes the probability given the number of nodes n, the number of edges e, and edge failure rate p. The problem of a uniformly optimally reliable graph is to find a graph that is optimal for all possible p. The graph studies are attracting more and more attention. Boesch et al. verified the existence of uniformly optimally reliable graphs when e = n, n + 1,n + 2 and given a conjecture for e = n + 3. In this work, a proof of the conjecture is given and it is proved that any min‐mi graph is 2‐connected. © 1994 by John Wiley & Sons, Inc.
Ripples, complements, and substitutes in singly constrained monotropic parametric network flow problems
Authors: Gautier Antoine , Granot Frieda 
Published: May 2007

AbstractWe extend the qualitative theory of sensitivity analysis for minimum‐cost flow problems developed by Granot and Veinott to minimum‐cost flow problems with one additional linear constraint. Two natural extensions of the “less dependent on” partial ordering of the arcs are presented. One is decidable in linear time, whereas the other yields more information but is NP‐complete in general. The Ripple Theorem gives upper bounds on the absolute value of optimal‐flow variations as a function of variations in the problem parameters. The theory of substitutes and complements presents necessary and sufficient conditions for optimal‐flow changes to consistently have the same (or the opposite) sign in two given arcs. The Monotonicity Theory links the changes in the value of the parameters to the change in the optimal arc‐flows, and bounds on the rates of changes are discussed. The departure from the pure network structure is shown to have a profound effect on computational issues. Indeed, the complexity of determining substitutes and complements, although linear for the unconstrained (no additional constraint) case, is shown to be NP‐complete in general for the constrained case. However, for all intractable problems, families of cases arise from easily recognizable graph structures which can be computed in linear time. © 1994 by John Wiley & Sons, Inc.
Maximum likelihood genetic sequence reconstruction from oligo content
Authors: Hagstrom Jane N. , Hagstrom Ray , Overbeek Ross , Price Morgan , Schrage Linus 
Published: May 2007

AbstractOne promising technique for determining long genetic sequences is sequencing by oligonucleotide content. This technique involves probing a segment of the unknown multimillion “character” genetic sequence for the presence or absence of known short subsequences. The information obtained from such hybridization experiments may be represented in network form. Network optimization methods may then be applied to identify the most likely forms of the unknown target sequence. © 1994 by John Wiley & Sons, Inc.
Topological properties, communication, and computation on WK‐recursive networks
Authors: Chen Gen‐Huey , Duh Dyi‐Rong 
Published: May 2007

AbstractRecently, with the support of the CAPRI (Concurrent Architecture and PRogramming environment for highly Integrated system) project, Vecchia and Sanges proposed a new general class of recursively scalable networks, termed WK‐recursive networks, and developed routing and broadcasting algorithms on them. They have also implemented the WK‐recursive networks using VLSI technology. This paper studies WK‐recursive networks by first investigating their topological properties such as diameter, connectivity, and Hamiltonicity. We then develop new and more efficient routing and broadcasting algorithms. Our routing algorithm can guarantee the shortest paths. Our broadcasting algorithm is much simpler and requires fewer extra bits to be transmitted. The broadcasting tree of our broadcasting algorithm is of minimal height (equal to the diameter), and each node receives the message exactly once. Moreover, we show the execution of descend/ ascend algorithms on the WK‐recursive networks using the bitonic sort as an illustrative example. © 1994 by John Wiley & Sons, Inc.
Applications of matching and edge‐coloring algorithms to routing in clos networks
Authors: Carpinelli John D. , Oruc A. Yavuz 
Published: May 2007

AbstractRearrangeable Clos networks have been studied in the literature in connection with telephone switching and communication networks. This paper examines the applicability of matching and edge‐coloring in bipartite graphs to the rearrangement problem in these networks. A survey of various matching and edge‐coloring algorithms is given, and these algorithms are evaluated for their suitability and effectiveness. It is shown that no single matching or edge‐coloring algorithm reported in the literature performs well over all Clos networks. It is further shown that the time complexity of the looping algorithm for Beneš networks is at least as good as any routing algorithm that can be obtained from matching or edge‐coloring. © 1994 by John Wiley & Sons, Inc.
New results for the degree/diameter problem
Authors: Dinneen Michael J. , Hafner Paul R. 
Published: May 2007

AbstractThe results of computer searches for large graphs with given (small) degree and diameter are presented. The new graphs are Cayley graphs of semidirect products of cyclic groups and related groups. One fundamental use of our “dense graphs” is in the design of efficient communication network topologies. © 1994 by John Wiley & Sons, Inc.