bluuebunny/crossref_metadata_2025_split huggingface dataset:
Network upgrading problems
Authors: Paik Doowon , Sahni Sartaj 
Published: May 2007

AbstractGraphs with weights and delays associated with their edges and/or vertices are often used to model communication and signal flow networks. Network performance can be improved by upgrading the network vertices. Such an upgrade reduces the edge/vertex delays and comes at a cost. We study different formulations of this network performance improvement problem and show that these are NP‐hard. We then consider one of the formulations and develop polynomial time algorithms for some special cases and pseudopolynomial time algorithms for others.
An exponential‐function reduction method for block‐angular convex programs
Authors: Grigoriadis Michael D. , Khachiyan Leonid G. 
Published: May 2007

AbstractAn exponential potential‐function reduction algorithm for convex block‐angular optimization problems is described. These problems are characterized byKdisjoint convex compact sets called blocks andMnon‐negative‐valued convex block‐separable coupling inequalities with a nonempty interior. A given convex block‐separable function is to be minimized. Concurrent, minimum‐cost, and generalized multicommodity network flow problems are important special cases of this model. The method reduces the optimization problem to two resource‐sharing problems. The first of these problems is solved to obtain a feasible solution interior to the coupling constraints. Starting from this solution, The algorithm proceeds to solve the second problem on the original constraints, but with a modified exponential potential function. The method is shown to produce an ϵ‐approximate solution inO(K(InM)(ϵ−2+ inK)) iterations, provided that there is a feasible solution sufficiently interior to the coupling inequalities. Each iteration consists of solving a subset of independent block problems, followed by a simple coordination step. Computational experiments with a set of large linear concurrent and minimum‐cost multicommodity network flow problems suggest that the method can be practical for computing fast approximations to large instances.
Feedback vertex set on cocomparability graphs
Authors: Coorg Satyan R. , Rangan C. Pandu 
Published: May 2007

AbstractGiven an undirected graph, The feedback vertex set problem is to find a set of vertices of minimum cardinality such that removing the vertices in this set makes the graph acyclic. This problem is known to be NP‐hard on general graphs. An O(n6) algorithm for this problem on permutation graphs is known. in this paper, we give an O(n4) algorithm for this problem on cocomparability graphs. Our result improves the time complexity of the algorithm and enlarges the class of graphs on which this problem is polynomial time‐solvable.
The symmetric generalized traveling salesman polytope
Authors: Fischetti Matteo , González Juan José Salazar , Toth Paolo 
Published: May 2007

AbstractThe symmetric Generalized Traveling Salesman Problem (GTSP) is a variant of the classical symmetric Traveling Salesman Problem, in which the nodes are partitioned into clusters and the salesman has to visit at least one node for each cluster. A different version of the problem, called E‐GTSP, arises when exactly one node for each cluster has to be visited. Both GTSP and E‐GTSP are NP‐hard problems and find practical applications in routing, scheduling, and location‐routing. in this paper, we model GTSP and E‐GTSP as integer linear programs and study the facial structure of the corresponding polytopes. in a companion paper, Theresults described in this work have been used to design a branch‐and‐cut algorithm for the exact solution of instances up to 442 nodes.
Antepenultimate broadcasting
Authors: Bermond Jean‐Claude , Fraigniaud Pierre , Peters Joseph G. 
Published: May 2007

AbstractBroadcasting is an information dissemination problem in which information originating at one node of a communication network (modeled as a graph) must be transmitted to all other nodes as quickly as possible. A broadcast graph is a graph which permits broadcasting from any originator in minimum time. in this paper, we present new methods for constructing sparse broadcast graphs. Our constructions are based on graph compounding operations which are relative to vertex sets with certain properties that depend on the broadcast protocols of the graphs. We show that many previous methods for constructing sparse broadcast graphs are special cases of our methods. We demonstrate our constructions by producing new sparse broadcast graphs and by showing how many previously constructed graphs can be obtained in a systematic way.
Hamilton cycles and paths in butterfly graphs
Authors: Wong Stephen A. 
Published: May 2007

AbstractA cycle C in a graph G is a Hamilton cycle if C contains every vertex of G. Similarly, a path P in G is a Hamilton path if P contains every vertex of G. We say that G is Hamilton‐connected if for any pair of vertices, u and v of G, There exists a Hamilton path from u to v. If G is a bipartite graph with bipartition sets of equal size, and there is a Hamilton path from any vertex in one bipartition set to any vertex in the other, The n G is said to be Hamilton‐laceable. We present a proof showing that the n‐dimensional k‐ary butterfly graph, denoted BF(k, n), contains a Hamilton cycle. Then, we use this result in proving the stronger result that BF(k, n) is Hamilton‐laceable when n is even and Hamilton‐connected for odd values of n.
An approach to a problem in network design using genetic algorithms
Authors: Palmer Charles C. , Kershenbaum Aaron 
Published: May 2007

AbstractThis paper describes a new approach to finding solutions to the optimal communication spanning tree problem (OCSTP) using a genetic algorithm. The difficulties posed by this problem are reviewed and a genetic algorithm that consistently finds very good, if not optimal, solutions to it is presented. Finally, a comparison of the genetic algorithm's solutions to those produced by a good heuristic is given that demonstrates the genetic algorithm's ability to find solutions at least equivalent to, if not superior to, those found by the heuristic.
The intractability of the reliable assignment problem in split networks
Authors: Stivaros Constantine , Sutner Klaus 
Published: May 2007

AbstractThe residual network reliability concerns networks with perfect edges and nodes that fail independently. It measures the probability that the network's operating nodes remain connected. The Assignment Problem deals with allocating given operating probabilities to the nodes of the network in such a way that the resulting residual network reliability is maximized. in this paper, we show that the Assignment Problem is computationally hard even for the restricted class of split networks, a generalization of threshold networks for which the problem is solvable in polynomial time.
Computing near‐optimal solutions to the steiner problem in a graph using a genetic algorithm
Authors: Esbensen Henrik 
Published: May 2007

AbstractA new genetic algorithm (GA) for the Steiner Problem in a Graph (SPG) is presented. The algorithm is based on a bitstring encoding of selected Steiner vertices and the corresponding Steiner tree is computed using a deterministic SPG heuristic. The GA is tested on all SPG instances from the OR‐Library having from 500 to 2500 vertices and up to 62,500 edges. For these graphs, The algorithm finds a global optimum in 70% of all program executions and is within 1% from the global optimum value in 90% of all executions. The performance is compared to that of two branch‐and‐cut algorithms and two of the very best deterministic heuristics: an iterated version of the Takahashi and Matsuyama heuristic (ITM) and an iterated version of the Kou, Markowsky, and Berman heuristic (IKMB). in almost all cases, even the worst result ever found by the GA is equal to or better than the best result of ITM and IKMB. Furthermore, while none of the deterministic heuristics or the branch‐and‐cut algorithms are capable of solving all problem instances within a reasonable time limit, The GA finds a near‐optimal solution to every problem in a moderate amount of time.
Reductions for the rectilinear steiner tree problem
Authors: Winter Pawel 
Published: May 2007

AbstractThe rectilinear Steiner tree problem asks for a shortest network connectingnterminals in the rectilinear plane (withL1‐metric). The problem can be considered as a special case of the Steiner tree problem in a grid network obtained by drawing horizontal and vertical lines through terminals. The reductions developed for the network variant of the Steiner tree problem can therefore also be used in the rectilinear case. However, computational experience indicates that they are not very powerful in the rectilinear grids. We introduce a limited number of rectilinear reductions based on the geometrical properties of terminals. Experimental results show that these reductions are extremely powerful while being quite simple to verify and easy to implement. For randomly generated problem instances with one terminal per row and column, The number of nonterminals remaining seems to be around 20‐‐25% of their original number. Furthermore, The performance of geometrical reductions improves as the density of terminals in fixed‐size grids grows.
Restricted simplicial decomposition with side constraints
Authors: Marín ÁNgel 
Published: May 2007

AbstractRestricted Simplicial Decomposition with Side Constraints is a price decomposition method designed for large‐scale nonlinear problems with a set of linear constraints with special structure and an additional set of linear side constraints. The resultant algorithm iterates by solving a linear subproblem subject to the set of structured constraints and a small nonlinear master problem whose feasible region is defined by the intersection of a simplex and the set of side constraints. The number of variables of the master problem is controlled by a parameter named r. The conditions required for the parameter r and the rules for dropping extreme points of the simplex are established for global convergence of the algorithm. Computational results are presented for nonlinear network problems with side constraints.
Reliability analysis of tree‐based networks and its application to fault‐tolerant VLSI systems
Authors: Roccetti Marco 
Published: May 2007

AbstractA probabilistic model is proposed that allows one to solve stochastic network reliability problems for tree‐type networks ofNnodes, takingO(logN) time. The considered networks are based on interconnection patterns consisting of complete binary trees in which spare edges are added according to different criteria. We show that the use of this probabilistic model allows one to evaluate, takingO(logN) time, Theaverage connectedness(i.e., The expected number of processing elements still functioning in the presence of random faults) of dynamically reconfigurable fault‐tolerant VLSI systems which are based on such tree‐based structures. Finally, numerical results obtained from the model are provided that show that, given a fixed chip silicon area, several of the analyzed VLSI architectures have a notably greater expected number of working processing elements w.r.t. complete binary trees, in the presence of a given fault distribution.
The pickup delivery location problem on networks
Authors: Mosheiov Gur 
Published: May 2007

AbstractThe Pickup Delivery Location Problem (PDLP) is a generalization of the Traveling Salesman Location Problem (TSLP) in which the daily tour involves pickup and delivery provided to customers by a vehicle of a given capacity. Two heuristics are suggested: The first is an extension of a method introduced by Simchi‐Levi and Berman for solving the TSLP. Its worst‐case relative error is shown to be bounded by 1. The second is based on a simple ranking of customers according to their probabilities for positive demand and their weighted average distances from all other locations. in addition, The fully polynomial algorithm of Berman and Simchi‐Levi is extended for solving PDLPs on tree networks. Both heuristics were tested on small‐size general networks and medium‐size tree networks. The average relative error over all test problems in the first class did not exceed 2.5% for the first heuristic and 1% for the second. in most cases, both produced the optimal solution. in about 56% of the tree network problems (with up to 80 nodes), Theoptimal home location of the server was found by at least one of the heuristics, and in about 94% of the problems, Theoptimal or an adjacent node was found by at least one of the heuristics.
Multiple message broadcasting in communication networks
Authors: Kwon Oh‐Heum , Chwa Kyung‐Yong 
Published: May 2007

AbstractBroadcasting refers to the process of dissemination of a set of messages originating from one node to all other nodes in a communication network. We assume that, at any given time, a node can transmit a message along at most one incident link and simultaneously receive a message along at most one incident link. We first present an algorithm for determining the amount of time needed to broadcastkmessages in an arbitrary tree. Second, we show that, for everyn, There exists a graph withnnodes whosek‐message broadcast time matches the trivial lower bound ⌈ logn⌉ +k− 1 by designing a broadcast scheme for complete graphs. We call those graphs minimal broadcast graphs. Finally, we construct annnode minimal broadcast graph with fewer than (⌈logn⌉ + 1)2⌈ logn⌉ −1edges.
The shortest path with at most / nodes in each of the series/parallel clusters
Authors: Li Wen‐Jui , Tsao H.‐S. Jacob , Ulular Osman 
Published: May 2007

AbstractWe study two related constrained shortest path problems in which the nodes are partitioned into series/parallel clusters. These and many other constrained shortest path problems occur in optimizing the layout of private networks embedded in a larger telecommunications network. The first problem deals with a situation in which, in addition to each edge being assigned a nonnegative integer weight, each node is also assigned a nonnegative integer weight, and the constraint on the path is that the total node weight incurred within each cluster should not exceed a given nonnegative integer /. The second problem considers two constraints: (i) a path cannot contain more than / nodes in one cluster and (ii) a path must traverse through at least one of a given set of special nodes in each of the traversed clusters. We propose efficient exact algorithms for solving both problems. Numerical examples are also provided.
An O(N2) heuristic for steiner minimal trees in E3
Authors: Smith J. MacGregor , Weiss Rich , Patel Minoo 
Published: May 2007

AbstractEven though the problem of computing Steiner minimal trees (SMTs) in the plane is well known to be NP‐hard, There exist heuristic algorithms which run in polynomial time. Recent research results have shown that the problem in three dimensions is demonstrably more difficult. This paper approaches the development of a heuristic for the problem utilizing the Delaunay triangulation in 3‐space to compute suboptimal SMTs. Computational results are also provided.
Encoding shortest paths in spatial networks
Authors: Erwig Martin 
Published: May 2007

AbstractA new data structure is presented which facilitates the search for shortest paths in spatially embedded planar networks in a worst‐case time of O(l log r), where l is the number of edges in the shortest path to be found and r is an upper bound on the number of so‐called cross edges (these are edges connecting, for any node v, different shortest path subtrees rooted at v's successors). The data structure is based on the idea to identify shortest path subtrees with the regions in the plane that they cover. in the worst case, The space requirement is O(rn), which, in general, is O(n2), but for regularly shaped networks, it is expected to be only O(n√n). A decomposition of graphs into biconnected components can be used to reduce the sizes of the trees to be encoded and to reduce the complexity of the regions for these trees. The decomposition also simplifies the algorithm for computing encoding regions, which is based on minimum link paths in polygons. Approximations for region boundaries can effectively be utilized to speed up the process of shortest path reconstruction: For a realistically constrained class of networks, i.e., networks in which the ratio of the shortest path distance between any two points to the Euclidean distance between these points is bounded by a constant, it is shown that an average searching time of O(l) can be achieved.
Decreased expression level of SH2 domain‐containing protein tyrosine phosphatase‐1 (Shp1) is associated with progression of chronic myeloid leukaemia
Authors: Amin HM , Hoshino K , Yang H , Lin Q , Lai R , Garcia‐Manero G 
Published: May 2007

AbstractChronic myeloid leukaemia (CML) is characterized by t(9;22)(q34;q11) and the aberrant expression of the fusion protein Bcr‐Abl that leads to constitutive activation of c‐Abl kinase. Bcr‐Abl plays a major role in the development and progression of CML through chronic, accelerated, and blast phases. The interaction between Bcr‐Abl and other oncogenic molecules has been extensively documented. Nonetheless, negative regulatory mechanisms of Bcr‐Abl are not completely defined. One major inhibitory pathway is mediated via the SH2 domain‐containing protein tyrosine phosphatase Shp1. In the present study, we demonstrate that Shp1 levels are markedly decreased in advanced stage CML patients compared with those in chronic phase. This process was independent of DNA methylation. Furthermore, we did not detect mutations in the Shp1 gene in CML cell lines or patient samples. These data suggest that the decrease in Shp1 in advanced stage CML patients is due to post‐transcriptional modifications. Our findings suggest that the decrease in Shp1 expression levels plays a role in the progression of CML. Also, the decrease in Shp1 and subsequently its inhibitory effect on Bcr‐Abl could provide an explanation for imatinib resistance seen in advanced stage CML patients. Copyright © 2007 Pathological Society of Great Britain and Ireland. Published by John Wiley & Sons, Ltd.
Computational study of the fluorination effect on nitrogen–boron bond
Authors: Liao Hsin‐Yi 
Published: May 2007

AbstractThe Lewis acid‐base H3−nFnN–BFmH3−m (n = 0–3; m = 0–3) system was examined using the density functional theory calculations. The NB bond strength can be adjusted stepwise by increasing the number of substituted fluorine atoms. The main finding of this work is the bond distances of the complexes do not correlate directly with the bond strengths. Some rationalization of this interesting observation was provided by the fluorine substitution effect on the HOMO‐LUMO gap, hybridization of bonding orbitals and electrostatic interaction. © 2007 Wiley Periodicals, Inc. Int J Quantum Chem, 2008
Poor enantioselectivity of the direct aldol reaction catalyzed by (S,S)‐proline dipeptide: A density functional study
Authors: Fan Jian‐Fen , Wu Li‐Fen , Tao Fu‐Ming 
Published: May 2007

AbstractDensity functional theory calculations were performed to study the stereo‐controlling step of the direct aldol reaction between acetone and 4‐nitrobenzaldehyde catalyzed by (S,S)‐proline dipeptide. Four transition state structures have been determined using B3LYP functional with the 6‐31G* basis set, corresponding to the anti and syn arrangements of the methylene moiety with respect to the carbonyl group in enamine intermediate, and to the si and re attacks to the aldehyde carbonyl carbon, respectively. Solvent effects of DMSO on the stereo‐controlling step were investigated with Onsager model. The energy results of the transition states reveal the origin of poor enantioselectivity for the reaction. © 2007 Wiley Periodicals, Inc. Int J Quantum Chem, 2008
Robust 24±6 ka 40Ar/39 Ar Age of a Low-Potassium Tholeiitic Basalt in the Lassen Region of NE California
Authors: Turrin Brent D. , Muffler L.J. Patrick , Clynne Michael A. , Champion Duane E. 
Published: May 2007

Abstract40Ar/39Ar ages on the Hat Creek Basalt (HCB) and stratigraphically related lava flows show that latest Pleistocene tholeiitic basalt with very low K2O can be dated reliably. The HCB underlies ∼ 15 ka glacial gravel and overlies four andesite and basaltic andesite lava flows that yield 40Ar/39Ar ages of 38±7 ka (Cinder Butte; 1.65% K2O), 46±7 ka (Sugarloaf Peak; 1.85% K2O), 67±4 ka (Little Potato Butte; 1.42% K2O) and 77±11 ka (Potato Butte; 1.62% K2O). Given these firm age brackets, we then dated the HCB directly. One sample (0.19% K2O) clearly failed the criteria for plateau-age interpretation, but the inverse isochron age of 26"6 ka is seductively appealing. A second sample (0.17% K2O) yielded concordant plateau, integrated (total fusion), and inverse isochron ages of 26±18, 30±20 and 24±6 ka, all within the time bracket determined by stratigraphic relations; the inverse isochron age of 24"6 ka is preferred. As with all isotopically determined ages, confidence in the results is significantly enhanced when additional constraints imposed by other isotopic ages within a stratigraphic context are taken into account.
Sedimentary responses to the Pleistocene climatic variations recorded in the South China Sea
Authors: Boulay Sébastien , Colin Christophe , Trentesaux Alain , Clain Stéphane , Liu Zhifei , Lauer-Leredde Christine 
Published: May 2007

AbstractGrain-size analyses, coupled with end-member modelling, have been performed on the terrigenous fraction of two Leg 184 Ocean Drilling Program sites (1144 and 1146) from the South China Sea. The grain-size distributions over the last 1.8 Ma enable a new interpretation of their connections to sea-level variations and East Asian monsoon strength. Previous investigations in this area have associated grain-size variability with enhanced eolian input during glacial stages. End-member modelling downgrades the importance of this eolian contribution and indicates that the sediments can be described as a mixture of three end-members: fluvial mud inputs, shelf reworking and river mouth migration. Grain-size variations in the Pleistocene section of the cores indicate a multiple-stage evolution: (i) from 1.8 to 1.25 Ma, the downcore grain-size variations are low but show a correspondence between monsoon rainfall intensity and the fine grain-sized fluvial inputs; no link with sea-level variations is noticeable; (ii) from 1.25 to 0.9 Ma, there is an increase (decrease) in the intermediate (fine) end-member (∼ 100 kyr cycle) that is associated with the onset of a stronger summer monsoon and modest shelf reworking; (iii) from 0.9 to 0 Ma the grain-size record is dominated by global sea-level variations; each glacial stage is associated with extensive shelf reworking and conveyance of coarse particles to the basin.
Bedload-to-suspended load ratio and rapid bedrock incision from Himalayan Landslide-dam lake record
Authors: Pratt-Sitaula Beth , Garde Michelle , Burbank Douglas W. , Oskin Michael , Heimsath Arjun , Gabet Emmanuel 
Published: May 2007

AbstractAbout 5400 cal yr BP, a large landslide formed a > 400-m-tall dam in the upper Marsyandi River, central Nepal. The resulting lacustrine and deltaic deposits stretched > 7 km upstream, reaching a thickness of 120 m.14C dating of 7 wood fragments reveals that the aggradation and subsequent incision occurred remarkably quickly (∼ 500 yr). Reconstructed volumes of lacustrine (∼ 0.16 km3) and deltaic (∼ 0.09 km3) deposits indicate a bedload-to-suspended load ratio of 1:2, considerably higher than the ≤ 1:10 that is commonly assumed. At the downstream end of the landslide dam, the river incised a new channel through ≥ 70 m of Greater Himalayan gneiss, requiring a minimum bedrock incision rate of 13 mm/yr over last 5400 yr. The majority of incision presumably occurred over a fraction of this time, suggesting much higher rates. The high bedload ratio from such an energetic mountain river is a particularly significant addition to our knowledge of sediment flux in orogenic environments.