bluuebunny/crossref_metadata_2025_split huggingface dataset:
Euclidean shortest paths in the presence of rectilinear barriers
Authors: Lee D. T. , Preparata F. P. 
Published: May 2007

AbstractIn this paper we address the problem of constructing a Euclidean shortest path between two specified points (source, destination) in the plane, which avoids a given set of barriers. This problem had been solved earlier for polygonal obstacles with the aid of the visibility graph. This approach however, has an Ω(n2) time lower bound, if n is the total number of vertices of the obstacles. Our goal is to find interesting cases for which the solution can be obtained without the explicit construction of the entire visibility graph. The two cases are (i) the path must lie within an n‐vertex simple polygon; (ii) the obstacles are n disjoint and parallel line segments. In both instances greedy O(n log n) time algorithms can be developed which solve the problems by constructing the shortest‐path tree from the source to all the vertices of the obstacles and to the destination.
Routing with time windows by column generation
Authors: Desrosiers Jacques , Soumis François , Desrochers Martin 
Published: May 2007

AbstractConsider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost, and a time interval within which the trip must begin. The trips may include visits to one or more specific points. Our problem is to determine the number of vehicles required, together with their routes and schedules, so that each trip begins within its given time interval, while the fixed costs related to the number of vehicles, and the travel costs between trips, are minimized. The problem is a generalization of the m‐traveling salesman problem. We use column generation on a set partitioning problem solved by simplex and branch‐and‐bound; columns are generated by a shortest path algorithm with time windows on the nodes. Numerical results for several school bus transportation problems with up to 151 trips are discussed.
Minimum cuts, modular functions, and matroid polyhedra
Authors: Cunningham William H. 
Published: May 2007

AbstractThe minimum cut problem is a well‐solved special case of submodular function minimization. We show that it is in fact equivalent to minimizing a modular function over a ring family. One‐half of this equivalence follows from classical work of Rhys and Picard. We give a number of applications to testing membership in special kinds of matroid polyhedra.
An efficiently solvable case of the minimum weight equivalent subgraph problem
Authors: Richey M. B. , Parker R. Gary , Rardin R. L. 
Published: May 2007

AbstractGiven a directed graph G(𝓋,𝒶), the problem of finding a minimum cardinality subset υ ⊆ 𝒶 such that the subgraph, G(𝓋,𝒶), preserves the reachability properties of G(𝓋,𝒶) is well known to be difficult. In this article, we consider a generalization which seeks a minimum weight subset υ satisfying the stated conditions where the weights of arcs in 𝒶 are assigned arbitrary integer values. A polynomial‐time algorithm is given for the case where the underlying, undirected graph is series‐parallel. Naturally, the stated algorithm subsumes the cardinality case on such graphs as well.
Locating a facility on a congested network with random lengths
Authors: Berman Oded 
Published: May 2007

AbstractThis article deals with a location problem on networks that are characterized by two types of uncertainties. The first type of uncertainties relates to the travel times on the network which are not deterministic but usually undergo random changes. The second type of uncertainties relates to the demands for service which may occur at different places in the network and at random times. The consequence of the second type of uncertainties is a system which may undergo periods of intense activity as well as other periods of relative inactivity. Previous research has dealt with each one of the two types of uncertainties separately. The objective of the paper is to locate a facility that garages a single server so as to minimize the expected cost of response. Results are obtained for two models. In one model demands that occur while the server is busy are rejected whereas in the other model queueing is allowed. The special case when the network is a tree is also considered.
An algorithm for the steiner problem in the euclidean plane
Authors: Winter Pawel 
Published: May 2007

AbstractAn algorithm for the exact solution of the Steiner problem in the Euclidean plane is presented. Compared with earlier algorithms, it generates full topologies in a different manner whereby the number of computations is substantially reduced. Furthermore, a large number of full Steiner trees which do not belong to the Steiner minimal tree is identified and discarded by new and efficient tests. The algorithm appears to be considerably faster than any other existing algorithm.
The Gilbert and Pollak conjecture—a generalization
Authors: Trietsch Dan , Handler Gabriel Y. 
Published: May 2007

AbstractGilbert and Pollak conjectured that the length of the minimal Steiner tree (MST) is at least \documentclass{article}\pagestyle{empty}\begin{document}$ \sqrt {3/4} $\end{document} that of the minimal spanning tree. In a subsequent paper, Gilbert generalized the Steiner tree problem by adding flow dependent weights to the arcs. We refer to the generalized problem as the Minimal Gilbert Network Problem, and to its optimal solution as the Minimal Gilbert Network (MGN). The purpose of this article is to generalize Gilbert and Pollak's conjecture to the ratio between the MGN and the regular minimal network (where extra nodes are not allowed). We prove that when the regular minimal network connects three nodes, the highest improvement possible, by adding exactly one extra point, is (2 − \documentclass{article}\pagestyle{empty}\begin{document}$ \sqrt 3 $\end{document})/2, and that this maximal improvement can be achieved only for the symmetric case, namely, where the three nodes are the vertices of an equilateral triangle and the weights of the three arcs are equal. As this is actually a Steiner tree case, we believe that the generalized and the original conjectures are equivalent, i.e., if this generalized conjecture will ever be disproved, the counterexample (or at least one of the possible counterexamples) would also disprove the original conjecture. Another result we present is a proof of the existence of the Gilbert generalized Steiner construction.
Probabilistic partitioning algorithms for the rectilinear steiner problem
Authors: Komlós János , Shing M. T. 
Published: May 2007

AbstractBased on the probabilistic approach introduced by Karp [14], we present two partitioning algorithms for the approximate solution of large instances of the rectilinear Steiner problem in the plane. The algorithms subdivide a set of given points into small groups, construct a minimum rectilinear Steiner tree for each small group, and then patch the subtrees together to form a near‐optimum rectilinear Steiner tree for the given points. Suppose there are n given points, uniformly distributed over the unit square [0,1] × [0,1] and spanned by a minimum rectilinear Steiner tree To. Then for any given integer t > 0, the first algorithm runs in O(f(t)n + n log n) time and produces a rectilinear Steiner tree T1 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_1 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞, while the second algorithm has an expected running time of O(g(t)n) and it also produces a rectilinear Steiner tree T2 such that \documentclass{article}\pagestyle{empty}\begin{document}$ \left({|T_2 |/|T_0 |} \right) \le 1 + O\left({\sqrt {1/t}} \right) $\end{document} with probability approaching 1 as n → ∞.
Reducing complexities of the distributed max‐flow and breadth‐first‐search algorithms by means of network synchronization
Authors: Awerbuch Baruch 
Published: May 2007

AbstractThis article presents new simple distributed Maximum Flow and Breadth‐First Search algorithms for an asynchronous communication network. Our algorithms improve the best known algorithms both in the communication and time complexities. The basic idea is first to “synchronize” the network and then to apply synchronous algorithms which use efficiently the parallelism of the model.
The average height of the d‐th highest leaf of a planted plane tree
Authors: Prodinger Helmut 
Published: May 2007

AbstractIt is proved that the dth highest leaf, where all planted plane trees with n nodes are assumed to be equally likely, has an average height \documentclass{article}\pagestyle{empty}\begin{document}$ \sqrt {\pi n} &#x02010; \frac{1}{2} &#x02010; \frac{2}{3}\sum\nolimits_{s = 1}^{d &#x02010; 1} {\left({2/9} \right)^s \left({\begin{array}{*{20}c} {2s + 1} \\ s \\ \end{array}} \right)} + O\left({n^{&#x02010; 1/2 + \varepsilon}} \right) $\end{document} for all ϵ > 0 and n → ∞. This solves a problem left open in one of our previous papers.
Configuration of physical distribution networks
Authors: Daganzo Carlos F. , Newell Gordon F. 
Published: May 2007

AbstractDistribution problems, including vehicle routing and warehouse location problems, are usually formulated by considering a finite number of possible locations for the customers, the warehouses, and vehicle stops. The question of selecting which of these points are actually used (and how) is a mixed‐integer programming problem which is difficult to solve. Thus, such a discrete formulation results in a problem that has to be solved heuristically; it also entails a large data preparation effort each time a solution has to be developed in response to changing world conditions. The continuous approach used in this paper attempts to circumvent some of these drawbacks. We consider one source and its customers in a service area; customer locations are modeled by a density surface over the service area. With this information, and data about the cost of inventory and transportation, we can determine the number of transhipment points, and the frequency and routing of all the distribution vehicles. An example is given. The continuous approach does not yield a solution. It gives design guidelines, which ensure near minimum total cost. These design guidelines are based on general properties of optimal solutions (discussed at the beginning of the paper) and on the specific characteristics of the case at hand. Implementation of the guidelines to obtain a feasible configuration requires human intervention. While the continuous method involves approximations (the real world is discrete and considerably more complicated than in our model), it yields insight into the structure of logistic systems. This insight should not only help in the design process; it may well also lead to improved heuristic solution methods for discrete formulations. Hybrid methods may eventually emerge.
Iterative algorithms for generating minimal cutsets in directed graphs
Authors: Shier D. R. , Whited D. E. 
Published: May 2007

AbstractSeveral approaches for evaluating network reliability require the generation of all minimal cutsets in a directed graph. A general iterative algorithm, based on an underlying algebraic structure, is proposed for generating all minimal s−j cutsets simultancously for all vertices j in such a graph. In order to implement this algorithm in an efficient manner and to exploit sparsity present in the graph, a number of computational simplifications are developed, leading to improved performance of the algorithm. Empirical results show that the choice of certain data structures can have a profound effect on the computational effort required.
On the worst‐case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints
Authors: Solomon Marius M. 
Published: May 2007

AbstractWe consider the vehicle routing and scheduling problem with time window constraints. Analytical results concerning the behavior of approximation methods for this problem class are derived through worst‐case analysis. For a variety of heuristics, it is shown that their worst‐case behavior on n customer problems is at least order of n for minimizing the number of vehicles used, the total distance traveled, and the total schedule time.
Optimally reliable graphs for both edge and vertex failures
Authors: Evans Trefor , Smith Derek 
Published: May 2007

AbstractThe problem of describing graphs representing a communication network which are optimally reliable has been studied both for the case of vertex failures and for the case of edge failures. We give a combinatorial definition in each case and show that under certain conditions the first definition implies the second. We use this result to investigate the existence of graphs which in some sense are optimally reliable with respect to both vertex and edge failures.
Network decomposition for the optimization of connection structures
Authors: Iwainsky Alfred , Canuto Enrico , Taraszow Oleg , Villa Agostino 
Published: May 2007

AbstractIn many practical situations, connection structures have to be laid out in an environment with a strong inner structure. This article presents a new general mathematical formulation of cor responding design problems in which the layout possibilities are represented by a network. Because in practice such networks are often very large and sparse, there is great interest in the utilization of decomposition techniques for the optimization of connection structures. New decomposition methods for the determination of optimal paths without interference (independent decom position), of k node‐disjoint paths with minimal total costs and of optimal Steiner trees are presented. The new methods are compared with other techniques under different aspects of practical importance.
A random network model of message transmission
Authors: Pullen Karen W. 
Published: May 2007

AbstractA model for message transmission through a network with unreliable nodes and links is presented; the assumptions are that nodes and links operate independently with probabilities α and β respectively. The following performance measures are derived: the probability of reaching k nodes by transmission m, the probability an arbitrary operable node is reached on the mth transmission, and the probability that d transmissions are required to reach all operable nodes. The algorithms are illustrated with a five‐node example network; some performance measures are shown graphically for a range of parameter values. This work was sponsored by the Electronic Systems Division of the United States Air Force Systems Command.
On multiple steiner subgraph problems
Authors: Richey M. B. , Parker R. Gary 
Published: May 2007

AbstractRecently, much attention has been given to the solvability of (otherwise intractable) combinatorial optimization problems when instances are confined to series‐parallel graphs. Substantially less is known, however, regarding those that remain hard on these particularly sparse structures. While a few ad hoc cases have been shown to be difficult, little appears to be known in terms of more generic settings. In this paper, we contend with this state of affairs by establishing that a class of Steiner subgraph‐like problems are NP‐complete on series‐parallel graphs while remaining easy (even trivial) on trees.
The node‐weighted steiner tree problem
Authors: Segev Arie 
Published: May 2007

AbstractThe general Node‐Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node‐associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP‐Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experiments.
Node partition formula for directed graph reliability
Authors: Buzacott J. A. 
Published: May 2007

AbstractCut set inclusion and exclusion is a well known reliability evaluation procedure. However, many of the cut set intersection terms cancel so it can be laborious to use. In directed graphs it is shown that the number of noncancelling terms cannot exceed the number of possible ordered partitions of the set of nodes. The resulting node partition formula will still contain cancelling terms when applied to incomplete graphs. An algorithm is developed to determine the set of noncancelling terms and its application illustrated on some special classes of graphs: acyclic graphs and graphs admitting a modular decomposition.
Postman tour on a graph with precedence relation on arcs
Authors: Dror Moshe , Stern Helman , Trudeau Pierre 
Published: May 2007

AbstractSince the introduction of the Chinese Postman Problem (CPP), many variations on the same theme have been developed. In this paper we examine still another variation. The arcs of the graph are partitioned and a precedence relation defined, specifying the order in which the elements of the partition have to be traversed. We first examine the conditions for a feasible solution to the problem. Next, we specify the graph properties of the precedence partition that insure a polynomial complexity solution of O(N5), where N is the number of nodes in the original graph. When the precedence relation on sets of arcs is general, we prove that the problem of finding the minimum length of feasible postman tour is NP‐complete.
On a function for the vulnerability of a directed flow network
Authors: Sengoku Masakazu , Shinoda Shoji , Yatsuboshi Reigo 
Published: May 2007

AbstractThe concept of vulnerability of a network, by which we mean the susceptibility of the network to attack, is very useful for the design of networks such as computer networks and communication networks. In this paper, a directed flow network, in which a nonnegative real number called edge capacity or capacity is associated with each edge is considered. If an edge in a network is destroyed, the value of maximum flow between two vertices in the network is decreased in general. If the decrease of the value of maximum flow by the destruction is large, the degree of influence of the edge on the vulnerability of the network is considered to be large. Two indices measuring the degree of influence of an edge on the vulnerability in the above sense are proposed and their properties are studied in this paper. Furthermore, the two indices are generalized to functions measuring the degree of influence of an edge on the vulnerability in a network.
A network flow algorithm to find an elementary I/O matching
Authors: Yamada Takeo 
Published: May 2007

AbstractLinnemann (Decoupling of structured systems. Syst. Contr. Lett. 1 (1981) 79‐86) proved that a linear square (m‐input, m‐output) dynamic system is structurally decouplable via a linear feedback if and only if there exists an elementary i/o matching in the graph representation of that system. This note supplements the above result by presenting an efficient network flow algorithm to find such a matching.
On graphs with signed inverses
Authors: Buckley Fred , Doty Lynne L. , Harary Frank 
Published: May 2007

AbstractA graph G is called invertible if its adjacency matrix A has an inverse which is the adjacency matrix of some graph H. All such graphs were shown by Harary and Minc to have the form nK2. We now introduce signed invertible (or briefly s‐invertible) graphs G as those whose inverse H is a signed graph. We identify two infinite classes of s‐invertible graphs: the paths P2n of even order, and the corona of any graph with K1. We then characterize s‐invertible trees.
Differential expression of AQP1 in microdomain‐enriched membranes of renal cell carcinoma
Authors: Ticozzi‐Valerio Davide , Raimondo Francesca , Pitto Marina , Rocco Francesco , Bosari Silvano , Perego Roberto , Sarto Cecilia , Di Fonzo Andrea , Bosso Niccolò , Mocarelli Paolo , Galli‐Kienle Marzia , Magni Fulvio 
Published: May 2007

AbstractHuman aquaporin‐1 (AQP1) is the most studied member of the aquaporin family, acting as molecular water channel. It is also considered a differentiation marker for proximal renal tubular cells, from which clear cells renal cell carcinoma (RCC) originates, playing an important role in urine formation. We therefore studied AQP1 expression at the proteomic level in RCC and normal tissues, mainly focusing on microdomain‐enriched membranes in which AQP1 is highly concentrated. Subcellular fractions were prepared through differential centrifugation, and microdomain‐enriched fractions were purified from a plasma membrane‐enriched fraction by 1% Triton X‐100 treatment followed by ultracentrifugation in sucrose gradient. After SDS‐PAGE and Western blot analyses with antibodies against AQP1, lower expression levels of AQP1 isoforms were observed in each subcellular fraction of RCC compared to fractions from normal kidney tissues. The presence of AQP1 in the immunoreactive bands was verified by MALDI‐TOF‐MS and LC‐ESI‐MS/MS analysis. Glycosylation of AQP1 was also investigated using N‐glycosidase F, confirming the presence of a N‐glycosylated isoform of AQP1 in the 35–45‐kDa region. These results highlight an under‐expression of AQP1 protein and its glycosylated isoforms in homogenate and subcellular fraction obtained from RCC tissue compared to adjacent normal cortex.
Anomalous U(1)'s, Chern‐Simons couplings and the Standard Model
Authors: Anastasopoulos P. 
Published: May 2007

AbstractThis proceeding is based on hep‐th/0605225 and it shows that the most general anomaly related effective action contains Stückelberg, axionic and Chern‐Simons‐like couplings. Such couplings are generically non‐trivial in orientifold string vacua. A similar analysis in quantum field theories provides similar couplings. These Chern‐Simons couplings generate new signals which might be visible at LHC.
Attractor black holes and quantum distribution functions
Authors: Montañez S. , Gómez C. 
Published: May 2007

AbstractUsing the attractor mechanism and the wavefunction interpretation of the topological string partition function on a Calabi Yau threefold M we study the relation between the Bekenstein‐Hawking‐Wald entropy of BPS Calabi‐Yau black holes and quantum distribution functions defined on H3(M). We discuss the OSV conjecture in this context. This talk is based on [1].
Gravitational theories coupled to matter as invariant theories under Kac‐Moody algebras
Authors: Tabti N. 
Published: May 2007

AbstractMany recent researches indicate that several gravitational D‐dimensional theories suitably coupled to some matter fields (including in particular pure gravity in D dimensions, the low energy effective actions of the bosonic string and the bosonic sector of M‐theory) would be characterized by infinite dimensional Kac‐Moody algebras 𝒢++ and 𝒢+++. The possible existence of these extended symmetries motivates a development of a new description of gravitational theories based on these symmetries. The importance of Kac‐Moody algebras and the link between the 𝒢+++‐invariant theories and the uncompactified space‐time covariant theories are discussed.
Tensor supermultiplets and toric quaternion‐Kähler geometry
Authors: de Wit B. , Saueressig F. 
Published: May 2007

AbstractWe review the relation between 4n‐dimensional quaternion‐Kähler metrics with n + 1 abelian isometries and superconformal theories of n + 1 tensor supermultiplets. As an application we construct the class of eight‐dimensional quaternion‐Kähler metrics with three abelian isometries in terms of a single function obeying a set of linear second‐order partial differential equations.