bluuebunny/crossref_metadata_2025_split huggingface dataset:
Incorporating dependent node damage in deterministic connectivity analysis and synthesis of networks
Authors: Heffes H. , Kumar A. 
Published: May 2007

AbstractSurvivability of a node vulnerable network is often assessed in terms of the (node) connectivity of the graph that represents the logical topology of the network. When the damage causing events have widespread impact then, owing to the physical layout of the network facilities, each event can destroy several nodes. As a survivability measure, therefore, we define the generalized connectivity as the minimum number of events (rather than the minimum number of node removals) required to disconnect the network. To model the possible effects of damage causing events, we introduce the notion of a dependence graph on the nodes of the network and a set of admissible cliques in this graph. Nodes that are nonadjacent in the dependence graph are independent, i. e., they cannot be damaged by the same event, and each event destroys an admissible clique of nodes. We present techniques for calculating or bounding the generalized connectivity of given network graphs, and for synthesizing minimum link networks with prescribed generalized connectivity.
Implementation of algorithms for K shortest loopless paths
Authors: Perko Aarni 
Published: May 2007

AbstractImplementations of loopless k shortest path algorithms are examined. Efficient storage structures for a large number of paths are given. A fast algorithm for determining the shortest paths in Yen's method is developed. Timing experiments show that a hybrid of Clarke's and Yen's methods is generally the fastest, although not significantly. Using upper bounds for the lengths of paths essentially improves all methods.
Minisum location of a traveling salesman
Authors: Berman O. , Levi D. Simchi 
Published: May 2007

AbstractIn this article we deal with the problem of locating on a network a service unit that must visit all the calls that are registered in a service list. Each node can generate a call with a given probability and the service list contains the first b calls that have arrived b ≤ n (n is the number of nodes). In our problem the optimal location minimizes the expected length of a traveling salesman tour (TST) traveled. For the problem (which requires 2n calculations of probabilities), we develop an O(n) Algorithm when b = n. for a tree, and study the sensitivity of this optimal solution when b < n.
On the number of active nodes in a multicomputer system
Authors: Barak Amnon , Drezner Zvi , Gurevich Yuri 
Published: May 2007

AbstractIn this article we develop probabilistic algorithms for estimating the number of active nodes in a multicomputer system which consists of independent computers that are interconnected by a communication network. The algorithms are based on routine exchange of messages among the nodes of the multicomputer, using random routing. We show that each active node can find an ϵ‐estimate of the fraction λ of active nodes in the system in time that depends only on ϵ and λ. The underlying approach can be used for finding various global properties of distributed systems with decentralized control.
First‐and second‐order bounds on terminal reliability
Authors: Assous J. Yael 
Published: May 2007

AbstractWe show that existing network algorithms solve the terminal reliability bound problem under limited information about the probabilities of operation of the components. Tightening of the bounds is achieved by introducing bounds on the probabilities that pairs of network components fail. A heuristic algorithm is developed to determine a tighter lower bound. The problem of the upper bound is also addressed. Our approach discards the traditional assumption of statistical independence of components' failures.
An approximation algorithm for the maximum independent set problem in cubic planar graphs
Authors: Choukhmane Elarbi , Franco John 
Published: May 2007

AbstractA polynomial time approximation algorithm A for the problem of finding a maximal independent set for cubic planar graphs is presented. It is shown that MA > 6/7 in the case of cubic planar graphs and MA = 7/8 in the case of triangle free cubic planar graphs where MA is the worst‐case ratio of the size of the independent set found by A to the size of the maximum independent set for the graph input to A.
Efficient points on a network
Authors: Hansen Pierre , Thisse Jacques‐Françols , Wendell Richard E. 
Published: May 2007

AbstractProperties of efficient points on a network are given. They are then used to devise (i) a linear algorithm for efficient points on a tree, (ii) on O(m log n) algorithm for the set of links common to all shortest paths between two points, and (iii) a polynomial algorithm for efficient points on a general network.
Improving reliability bounds in computer networks
Authors: Brecht Timothy B. , Colbourn Charles J. 
Published: May 2007

AbstractThe probability that a computer network is operational in an environment of statistically independent link failures has been widely studied. Three natural problems arise, when all nodes are to be connected (all‐terminal reliability), when two nodes are to communicate (2‐terminal reliability), and when k specified nodes are to communicate (k‐terminal reliability); the latter case includes the first two. Each of these reliability measures is NP‐hard to compute, and thus efficiently computable reliability bounds are of significant interest. To date, the all‐terminal and 2‐terminal cases have been treated separately, and few results apply to the k‐terminal case. In this paper, we develop a simple strategy to obtain k‐terminal reliability bounds. In the process, we demonstrate improvements on the previous best bounds for all‐terminal, k‐terminal, and 2‐terminal reliability. Computational experience with these new bounds is reported, by comparing the new lower bounds to existing lower bounds.
Domination and location in acyclic graphs
Authors: Slater Peter J. 
Published: May 2007

AbstractLocating‐dominating sets are of interest in safeguard applications of graphical models of facilities. A subset S of the vertex set V of a graph G is a dominating set if each vertex u ϵ V ‐ S is adjacent to at least one vertex in S. For each v in V ‐ S let S(v) denote the set of vertices in S which are adjacent to v. A dominating set S is defined to be “locating” if for any two vertices v and w in V ‐ S one has S(v) ≠ S(w). Sharp bounds on the cardinality of locating‐dominating sets for arbitrary graphs on p vertices and for trees on p vertices are given, and a linear (that is O(P)) algorithm for finding a minimum cardinality locating‐dominating set in an acyclic graph is presented.
Investing in arcs in a network to maximize the expected max flow
Authors: Wallace Stein W. 
Published: May 2007

AbstractConsider a network with arcs subject to failures. We show how the problem of investing in new arcs in such a network in order to increase the expected max flow as much as possible can be formulated as a stochastic program with network recourse. We show how to decompose the problem, and consider both exact methods and approximations. Convergence proofs are given. We demonstrate that max flow recourse problems can be solved very efficiently, since lower and upper bounds are equally simple to evaluate.
Forbidden subgraphs and graph decomposition
Authors: Wagner Donald K. 
Published: May 2007

AbstractSeries‐parallel graphs, outerplanar graphs, and graphs whose polygon matroids are transversal have been characterized by forbidden subgraphs. Tutte introduced a graph decomposition for nonseparable graphs. The results of this paper relate the existence of the forbidden subgraphs to properties of the decomposition. Algorithmic implications are considered.
On the properties of directed switching networks
Authors: Wu Min‐You , Chan Shu‐Park 
Published: May 2007

AbstractThe theory of directed switching networks is developed. After the fundamental concepts are defined, the rank of the path matrix of a Directed Single‐Contact (Di‐SC) network is discussed. The theorem which gives the essential relationship between the SC and Di‐SC networks is proved. Then the Odd‐Addition‐Subtraction (OAS) condition is given as a necessary condition for Di‐SC functions. The analysis of directed switching networks and the synthesis of Di‐SC networks are also given for practical applications. The results could be used in the design of electrical and computer systems with directed elements.
On some matching problems arising in vehicle scheduling models
Authors: Bertossi A. A. , Carraresi P. , Gallo G. 
Published: May 2007

AbstractTwo bipartite matching problems arising in Vehicle Scheduling are considered: the capacitated matching and the multicommodity matching. For the former, given a reasonable cost structure, we can exhibit a polynomial time algorithm, while the general case is conjectured to be NP‐hard. The latter problem is shown to be NP‐hard. A heuristic algorithm based on Lagrangean relaxation for the capacitated version of the multicommodity matching is also presented together with experimental results.
Digraphs with maximum number of paths and cycles
Authors: Perl Yehoshua 
Published: May 2007

AbstractWe construct a digraph with the maximum number of simple paths between two specified vertices, for a digraph with a given number of edges. The following cases are considered: digraphs with parallel edges, acyclic simple digraphs and general simple digraphs. The corresponding extremal digraphs are the tri‐chains, the (deficient) Fibonacci digraphs and (if our conjecture is true) the 3‐diamond strings, respectively. The similarity of these three families of digraphs is discussed. The related problem of digraphs with the maximum number of simple cycles for a given number of edges is considered too.
Data transfers in networks with transceivers
Authors: Choi Hyeong‐Ah , Hakimi S. Louis 
Published: May 2007

AbstractThe scheduling of data transfers in networks, where the schedule does not permit interruption and each communication module can be used as a transmitter and as a receiver (i.e., as a transceiver) was studied by Coffman et al. The same problem when interruption in the schedule is permitted and the transmitting and receiving modules are distinct was studied by Choi and Hakimi among others. Hajek and Sasaki studied another interesting variation of the problem where interruption is permitted but each communication module is a transmitter and a receiver. This paper presents certain generalizations and improvements of Hajek and Sasaki's results.
Algorithms for maximum k‐colorings and k‐coverings of transitive graphs
Authors: Gavril Fǎnicǎ 
Published: May 2007

AbstractConsider a graph G and a positive integer k. The maximum k‐coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k‐covering problem is to find k disjoint cliques covering a maximum number of vertices. The present paper contains polynomial time algorithms for finding maximum k‐colorings and maximum k‐coverings of transitive graphs.
Probabilistic analysis of the longest hamiltonian tour problem
Authors: Vohra Rakesh V. 
Published: May 2007

AbstractIn this paper we study the probabilistic behavior of the farthest neighbor heuristic for finding the longest Hamiltonian tour in a graph. We assume the edge weights are independent random variables uniformly distributed in [0,1]. If F, is the length of the heuristic tour and L, the optimal tour then Fn/Ln → 1 a.s. as n → α. We also show that Ln/n → 1 a.s. as n → ∞.
On a property of cyclic covers of p‐graphs
Authors: Politof Themistocles 
Published: May 2007

AbstractA directed graph G with a source s and a sink t is called a p‐graph if every edge of G belongs to an elementary (s,t)‐path of G. If C is a cycle of the p‐graph G then a cyclic cover of C is a set of (s,t)‐paths of G that contains all the edges of C. A cyclic cover Q is minimal if for every path P e Q, Q = {P} is not a cover of C. The following property is known and was used in providing an important result in network reliability: A cyclic p‐graph has a cycle C and a path P such that P is not contained in any minimal cover of C. In this note we give a simpler proof of this property which provides more insight into the nature of cyclic covers in p‐graphs.
A single‐server priority queueing‐location model
Authors: Batta Rajan , Larson Richard C. , Odoni Amedeo R. 
Published: May 2007

AbstractThis paper considers the problem of locating a single server on a network, relaxing the assumption that the server is always available for service, and explicitly accounting for queueing. The resulting queueing‐location model allows for an arbitrary number of priority classes. Properties of the objective function are developed and algorithms presented for obtaining the optimal location on tree and cyclic networks. Sensitivity analysis with respect to the average arrival rate of calls is investigated. A numerical example is presented to illustrate the results of this paper. The major conclusions of the paper include: (a) the optimal location need not be at a node of the network, (b) the optimal location changes as a function of the arrival rate of calls into the system, (c) the optimal location is usually different from that obtained by grouping all calls into one priority class.
Vertex domination‐critical graphs
Authors: Brigham Robert C. , Chinn Phyllis Z. , Dutton Ronald D. 
Published: May 2007

AbstractA dominating set in a graph G is a set of vertices D such that every vertex of G is either in D or is adjacent some vertex of D. The domination number Γ(G) of G is the minimum cardinality of any dominating set. A graph is vertex domination‐critical if the removal of any vertex decreases its domination number. This paper gives examples and properties of vertex domination‐critical graphs, presents a method of constructing them, and poses some open questions. In the process several results for arbitrary graphs are presented.
Contribution of laser microdissection‐based technology to proteomic analysis in hepatocellular carcinoma developing on cirrhosis
Authors: Dos Santos Alexandre , Thiers Valérie , Sar Sokhavuth , Derian Nicolas , Bensalem Noura , Yilmaz Funda , Bralet Marie‐Pierre , Ducot Béatrice , Bréchot Christian , Demaugre France 
Published: May 2007

AbstractHepatocellular carcinoma (HCC) is a major cause of cancer worldwide. Proteomic studies provide opportunities to uncover targets for the diagnosis and treatment of this disease. However, in HCC developing in a setting of cirrhosis, the detection of proteome alterations may be hampered by the increased cellular heterogeneity of tissue when analysing global liver homogenates. The aim of this study was to evaluate whether the identification of proteome alterations in these HCC cases was improved when the differential protein profile between tumour and non‐tumour areas of liver was determined using hepatocytes isolated by laser microdissection (LM). Differential profiles established with LM‐hepatocytes and liver section homogenates using 2‐DE and MS exhibited noticeable differences: 30% of the protein spots with deregulated expression in tumorous LM‐samples did not display any modification in homogenates; conversely 15% of proteins altered in tumorous homogenates were not impaired in LM‐hepatocytes. These alterations resulted from the presence in cirrhotic liver of fibrotic stroma which displayed a protein pattern different from that determined in LM‐hepatocytes. In conclusion, our data demonstrate the interest of LM in distinguishing between fibrotic and hepatocyte proteome alterations and thus the benefit of LM to proteome studies of HCC developing in a context of cirrhosis.
Non‐linear realizations, super branes and kappa symmetry
Authors: Gomis J. , Kamimura K. , West P. 
Published: May 2007

AbstractWe will show how the theory of non‐linear realizations can be used to naturally incorporate kappa transformations for the superpoint particle. Similar results also hold for a general super p‐brane, however we must in these cases include an additional Lorentz transformation.
Adding magnetic flux to the baryon vertex
Authors: Janssen B. , Lozano Y. , Rodríguez‐Gómez D. 
Published: May 2007

AbstractWe generalise the baryon vertex configuration of AdS/CFT by adding magnetic field on its worldvolume, dissolving D‐string charge. A careful analysis of the configuration shows that there is an upper bound on the number of dissolved strings. We provide a microscopical description of this configuration in terms of a dielectric effect for the dissolved strings.
Entropy of three‐charge black holes on a circle
Authors: Harmark T. , Kristjánsson K.R. , Obers N.A. , Rønne P.B. 
Published: May 2007

AbstractWe study phases of five‐dimensional three‐charge black holes with a circle in their transverse space. In particular, when the black hole is localized on the circle we compute the corrections to the metric and corresponding thermodynamics in the limit of small mass. When taking the near‐extremal limit, this gives the corrections to the finite entropy of the extremal three‐charge black hole as a function of the energy above extremality. For the partial extremal limit with two charges sent to infinity and one finite we show that the first correction to the entropy is in agreement with the microscopic entropy by taking into account that the number of branes shift as a consequence of the interactions across the transverse circle.
The Hagedorn temperature in a decoupled sector of AdS/CFT
Authors: Harmark T. , Kristjansson K. , Orselli M. 
Published: May 2007

AbstractWe match the Hagedorn/deconfinement temperature of planar 𝒩 = 4 super Yang‐Mills (SYM) on ℝ × S3 to the Hagedorn temperature of string theory on Ads5 × S5. The match is done in a near‐critical region where both gauge theory and string theory are weakly coupled. On the gauge theory side we are taking a decoupling limit found in [7] in which the physics of planar 𝒩 = 4 SYM is given exactly by the ferromagnetic XXX1/2 Heisenberg spin chain. We find moreover a general relation between the Hagedorn/deconfinement temperature and the thermodynamics of the Heisenberg spin chain. On the string theory side, we identify the dual limit which is taken of string theory on a maximally symmetric pp‐wave background with a flat direction, obtained from a Penrose limit of Ads5 × S5. We compute the Hagedorn temperature of the string theory and find agreement with the Hagedorn/deconfinement temperature computed on the gauge theory side. Finally, we discuss a modified decoupling limit in which planar 𝒩 = 4 SYM reduces to the XXX1/2 Heisenberg spin chain with an external magnetic field.
Supersymmetry and cosmic censorship
Authors: Ortín T. 
Published: May 2007

AbstractWe show that requiring unbroken supersymmetry everywhere in black‐hole‐type solutions of N = 2, d = 4 supergravity coupled to vector supermultiplets ensures in most cases absence of naked singularities. We show that the requirement of global supersymmetry implies the absence of sources for NUT charge, angular momentum, scalar hair and negative energy, for which there is no microscopic interpretation in String Theory. These conditions exclude, for instance, singular solutions such as the Kerr‐Newman with M = |q|, which fails to be everywhere supersymmetric. There are, nevertheless, everywhere supersymmetric solutions with global angular momentum and non‐trivial scalar fields. We also present similar preliminary results in N = 1, d = 5 supergravity coupled to vector multiplets.
Orientifolding in N = 2 superspace
Authors: Robles‐Llana D. , Roček M. , Saueressig F. , Theis U. , Vandoren S. 
Published: May 2007

AbstractWe discuss orientifold projections on superspace effective actions for hypermultiplets. We present a simple and new mechanism that allows one to find the Kähler potential and complex structure for the N = 1 theory directly in terms of the parent N = 2 theory. As an application, we demonstrate our method for Calabi‐Yau orientifold compactifications of type IIB superstrings.
Probe D‐branes in superconformal field theories
Authors: Edelstein J.D. 
Published: May 2007

AbstractWe overview the main configurations of D‐brane probes in the AdS5 × X5 background of type IIB string theory (X5 being a Sasaki–Einstein manifold), and examine their most salient features from the point of view of the dual quiver superconformal field theory.
Parafermions, brane distributions and FRW hierarchies
Authors: Petropoulos P.M. 
Published: May 2007

AbstractI review a class of exact string backgrounds, which appear in hierarchies, where the boundary of the target space of an exact sigma model is itself the target space of another exact model. From the worldsheet viewpoint this is due to the existence of (1,1) operators based on parafermions. From the target space side, it is reminiscent of the structure of maximally symmetric Friedmann–Robertson–Walker cosmological solutions, with broken homogeneity though. Cosmological evolution in this framework raises again the question of the nature of time in string theory.
Product CFTs, gravitational cloning, massive gravitons and the space of gravitational duals
Authors: Kiritsis E. 
Published: May 2007

AbstractThe question of graviton cloning in the context of the bulk/boundary correspondence is considered. It is shown that multi‐graviton theories can be obtained from products of large‐N CFTs. No more than one interacting massless graviton is possible. There can be however, many interacting massive gravitons that can be arbitrarily light. This is achieved by coupling CFTs via multi‐trace marginal or relevant perturbations. The geometrical structure of the gravitational duals of such theories is that of product manifolds with their boundaries identified. The interpretation of such theories is discussed. Potential applications to massive gravity and cosmology are briefly suggested.
High‐power pure blue laser diodes
Authors: Ohta M. , Ohizumi Y. , Hoshina Y. , Tanaka T. , Yabuki Y. , Funato K. , Tomiya S. , Goto S. , Ikeda M. 
Published: May 2007

AbstractWe successfully developed high‐power and long‐lived pure blue laser diodes (LDs) having an emission wavelength of 440–450 nm. The pure‐blue LDs were grown by metalorganic chemical vapor deposition (MOCVD) on GaN substrates. The dislocation density was successfully reduced to ∼106 cm–2 by optimizing the MOCVD growth conditions and the active layer structure. The vertical layer structure was designed to have an absorption loss of 4.9 cm–1 and an internal quantum efficiency of 91%. We also reduced the operating current density to 6 kA/cm2 under 750 mW continuous‐wave operation at 35 °C by optimizing the stripe width to 12 µm and the cavity length to 2000 µm. The half lifetimes in constant current mode are estimated to be longer than 10000 h. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)