bluuebunny/crossref_metadata_2025 huggingface dataset:
Berlin's Changing Memory Landscape: New Scholarship in German and English
Authors: Wüstenberg Jenny
Published: May 2007

Claus Leggewie and Erik Meyer, “Ein Ort, an den man gerne geht” Das Holocaust-Mahnmal und die deutsche Geschichtspolitik nach 1989 (Munich: Carl Hanser Verlag, 2005)

Karen E. Till, The New Berlin: Memory, Politics, Place (Minneapolis: University of Minnesota Press, 2005)

Peter Carrier, Holocaust Monuments and National Memory Cultures in France and Germany since 1989: The Origins and Political Function of the Vél’ d’Hiv’ in Paris and the Holocaust Monument in Berlin (New York: Berghahn Books, 2005)
"We Don't Want To Be the Jews of Tomorrow": Jews and Turks in Germany after 9/11
Authors: Yurdakul Gökçe
Published: May 2007

This article examines how German Turks employ the German Jewish trope to establish an analogous discourse for their own position in German society. Drawing on the literature on immigrant incorporation, we argue that immigrants take more established minority groups as a model in their incorporation process. Here, we examine how German Turks formulate and enact their own incorporation into German society. They do that, we argue, by employing the master narrative and socio-cultural repertoire of Germany's principal minority, German Jewry. This is accomplished especially in relation to racism and antisemitism, as an organizational model and as a political model in terms of making claims against the German state. We argue that in order to understand immigrant incorporation, it is not sufficient to look at state-immigrant relations only—authors also need to look at immigrant groups' relationships with other minority groups.
Ueber die Wirkung nicht‐leitender Körper bei der elektrischen Induction
Authors: Faraday M. , Riess P.
Published: May 2007

Der nachfolgende Brief erklärt sich selbst. Ich habe darauf eine sehr verbindliche Antwort von Hrn. Riess erhalten, welche ich demselben hinzuzufügen wünsche. Ich habe das Englische der Antwort ein wenig geändert, hauptsächlich in einzelnen kleinen Worten und nur in solchen Fällen, wo ich glaubte, die Aenderung würde die Meinung des Verfassers klarer machen. Gewisse Ausdrücke von Hrn. Riess verlangen fast eine Antwort. In Bezug auf diese Fälle und um Zweideutigkeit in Betreff meiner eignen Meinung zu entfernen, habe ich gewagt, einige Anmerkungen hinzuzufügen, nicht um eine Discussion über Hypothesen zu erregen, sondern um meine Ansicht (dem Leser) zu erläutern. Es ist nicht die Pflicht oder das Amt eines Naturforschers Glauben zu dictiren, und jede Hypothese ist mehr oder weniger Sache des Glaubens; er hat nur seine Thatsachen und seine Schlüsse zu geben, und so viel von der Logik, welche die ersteren mit den letzteren verknüpft, als er für nothwendig halten mag; dann hat er das Ganze der wissenschaftlichen Welt zur gegenwärtigen, und, wie er zuweilen ohne Anmassung glauben darf, zur künftigen Beurtheilung zu überliefern.
Expression of two recombinant chloramphenicol acetyltransferase variants in highly reduced genome Escherichia coli strains
Authors: Sharma Shamik S. , Campbell John W. , Frisch David , Blattner Frederick R. , Harcum Sarah W.
Published: May 2007

Highly reduced E. coli strains, MDS40, MDS41, and MDS42, lacking approximately 15% of the genome, were grown to high cell densities to test their ability to produce a recombinant protein with high yields. These strains lack all transposons and insertion sequences, cryptic prophage and many genes of unknown function. In addition to improving genetic stability, these deletions may reduce the biosynthetic requirements of the cell potentially allowing more efficient production of recombinant protein. Basic growth parameters and the ability of the strains to produce chloramphenicol acetyltransferase (CAT) under high cell density, batch cultivation were assessed. Although growth rate and recombinant protein production of the reduced genome strains are comparable to the parental MG1655 strain, the reduced genome strains were found to accumulate significant amounts of acetate in the medium at the expense of additional biomass. A number of hypotheses were examined to explain the accumulation of acetate, including oxygen limitation, carbon flux imbalance, and metabolic activity of the recombinant protein. Use of a non‐catalytic CAT variant identified the recombinant protein activity as the source of this phenomenon; implications for the metabolic efficiency of the reduced genome strains are discussed. Biotechnol. Bioeng. 2007;98: 1056–1070. © 2007 Wiley Periodicals, Inc.
Studies on aerosol delivery of plasmid DNA using a mesh nebulizer
Authors: Arulmuthu Eugene R. , Williams David J. , Baldascini Helen , Versteeg Henk K. , Hoare Mike
Published: May 2007

Aerosol delivery of plasmid DNA therapeutic solutions is promising for the treatment of respiratory diseases. However, it poses challenges, most significantly the need to protect the delicate supercoiled (sc) structure of plasmid during aerosolization. Nebulizers for liquid aerosolization using meshes appear a better method for delivery than conventional jet and ultrasonic nebulizers. This paper explores their application to the delivery of plasmid DNA. A computational fluid dynamics model of the dynamics of fluid flow through the nozzle of the MicroAIR® mesh nebulizer indicated high strain rates (>105 s−1) near the nozzle exit capable of causing damage to the shear‐sensitive plasmid DNA. Knowledge of the strain rates predicted using CFD and molecule size determined using atomic force microscopy (AFM) enabled estimation of the hydrodynamic force and whether damage of shear‐sensitive therapeutics was likely. Plasmids of size 5.7 and 20 kb were aerosolized in the mesh nebulizer. The sc structure of the 5.7‐kb plasmid was successfully delivered without damage, while aerosolization of the 20‐kb plasmid led to disintegration of the pDNA sc structure as observed in AFM. Subsequent formulation of the sc 20‐kb plasmid with PEI resulted in successful aerosol delivery. The maximum hydrodynamic forces computed for the aerosolization of structures of the size of 5.7‐kb and PEI formulated 20‐kb plasmids were less than the forces reported to damage the structure of double‐stranded DNA. A combination of CFD analysis and structure analysis may be used to predict successful aerosol delivery in such a mesh nebulizer. Biotechnol. Bioeng. 2007;98: 939–955. © 2007 Wiley Periodicals, Inc.
Coupling kinetic expressions and metabolic networks for predicting wine fermentations
Authors: Pizarro Francisco , Varela Cristian , Martabit Cecilia , Bruno Claudio , Pérez‐Correa J. Ricardo , Agosin Eduardo
Published: May 2007

Problematic fermentations are commonplace and cause wine industry producers substantial economic losses through wasted tank capacity and low value final products. Being able to predict such fermentations would enable enologists to take preventive actions. In this study we modeled sugar uptake kinetics and coupled them to a previously developed stoichiometric model, which describes the anaerobic metabolism of Saccharomyces cerevisiae. The resulting model was used to predict normal and slow fermentations under winemaking conditions. The effects of fermentation temperature and initial nitrogen concentration were modeled through an efficiency factor incorporated into the sugar uptake expressions. The model required few initial parameters to successfully reproduce glucose, fructose, and ethanol profiles of laboratory and industrial fermentations. Glycerol and biomass profiles were successfully predicted in nitrogen rich cultures. The time normal or slow wine fermentations needed to complete the process was predicted accurately, at different temperatures. Simulations with a model representing a genetically modified yeast fermentation, reproduced qualitatively well literature results regarding the formation of minor compounds involved in wine complexity and aroma. Therefore, the model also proves useful to explore the effects of genetic modifications on fermentation profiles. Biotechnol. Bioeng. 2007;98: 986–998. © 2007 Wiley Periodicals, Inc.
Fate of the primary
Authors: Hughes Charles Evans
Published: May 2007

As Charles Evans Hughes presented the case in 1920 for party responsibility open to insurgency.
The perils of ‘sharing’
Authors: Anderson William
Published: May 2007

An old master counters myths about “free money,” sees dangers of further weakening of the states.
The value of bigness
Authors: Chute Charlton F.
Published: May 2007

New York State, including local units in purchasing setup, sets new goals in intergovernmental relations.
Widening the scope
Authors: Holland Lynwood M.
Published: May 2007

Atlanta region finds lack of knowledge, confidence major obstacles to metropolitan problem solving.
At the bargaining table
Authors: Berrodin Eugene F.
Published: May 2007

State laws, federal standards differ greatly on rights of public employee unions and duties of the employers.
New aids for cities
Authors: Simpson Philip G.
Published: May 2007

State agencies for local affairs can help provide effective coordination of services.
Time for a change
Authors: Wyatt Wilson W.
Published: May 2007

An incentive system may be key to effective local government through merging functions.
The social marketplace
Authors: Jones Charles F.
Published: May 2007

Business leader urges ‘eyeball‐to‐eyeball’ contact and corporate involvement to solve urban problems.
Too costly politics
Authors: Alexander Herben E.
Published: May 2007

As parties default on federal controls, states are warned to handle problem imaginatively.
Community the key
Authors: Slingsby Stephen D.
Published: May 2007

This principle should be kept paramount with population equality in legislative redistricting.
Breaking the barrier
Authors: Kolesar John N.
Published: May 2007

New Jersey experience suggests need for new definitions, wider state action on urban problems.
No more law's delay
Authors: Bloom Murray Teigh
Published: May 2007

In Pittsburgh area, stern methods and hard work cut backlog of cases and reduce taxpayers' bill.
No simple solution
Authors: Bone Hugh A.
Published: May 2007

Reform of state party structures and functions cannot be generalized into a single formula.
A working agreement
Authors: Zimnermann Frederick L.
Published: May 2007

Interstate compacts may be most versatile and effective instruments to achieve coordination.
Electing the president
Authors: Gossett William T.
Published: May 2007

Bar Association chief calls direct popular vote the only worthy reform of the present system.
Shape of the future
Authors: Lehne Richard
Published: May 2007

Suburbs seen as biggest bloc in Congress for the first time after 1970 reapportionment.
The voters' voice
Authors: Sittig Robert F.
Published: May 2007

New York's ‘challenge’ primary passes first test in democratizing nominating process.
For annual sessions
Authors: Owsley Roy H.
Published: May 2007

Trend toward continuity for legislatures grows as Kentucky faces enabling amendment.
A growing trend
Authors: Zimmerman Joseph F.
Published: May 2007

State agencies for local affairs moving from advisory to coordinating and operating roles.
Computing equilibria on large multicommodity networks: An application of truncated quadratic programming algorithms
Authors: Dembo Ron S. , Tulowitzki Ulrich
Published: May 2007

We present a general scheme for improving the asymptotic behavior of a given nonlinear programming algorithm without incurring a significant increase in storage overhead. To enhance the rate of convergence we compute search directions by partially solving a sequence of quadratic programming (QP) problems as suggested by Dembo [6]. The idea is illustrated on a class of extremely large nonlinear programming problems arising from traffic equilibrium calculations using both the Frank‐Wolfe and PARTAN algorithms to partially solve the QP subproblems. Computational results indicate that the convergence rate of the underlying algorithm is indeed enhanced significantly when Frank‐Wolfe is used to solve the QP subproblems but only marginally so in the case of PARTAN. It is conjectured, and supported by the theory [11], that with better algorithms for the QP subproblems the improvements due to the proposed framework would be more marked.
Minimum‐delay routing in continuous‐time dynamic networks with Piecewise‐constant capacities
Authors: Ogier Richard G.
Published: May 2007

A single‐source single‐sink dynamic network is considered where the link flows are real‐valued measurable functions defined on a time interval and where storage is allowed at the nodes. Piecewise‐constant link and storage capacities are given. A τ‐maximum flow is a dynamic flow assignment that maximizes the total amount of commodity reaching the sink before time τ. The problem considered is that of computing a flow which is simultaneously τ‐maximum for all τ. Such a flow solves a minimum‐delay dynamic routing problem. An algorithm is presented which computes an optimal flow in O( | N | 4T4) time, where | N | is the number of nodes and T is the number of times that the capacities change. Previous polynomial‐time algorithms have been given only for the case of constant capacities.
Solving nonlinear multiple‐facility network location problems
Authors: Hooker J. N.
Published: May 2007

We show how to locate optimally p new facilities (servers) on a network so as to minimize cost, where cost can be any convex function of the distances between demand points (nodes) and a closest server. The algorithm is generally practical only for small p (perhaps 2, 3, or 4), but it admits a large number of servers with locations fixed beforehand. The classical p‐median, p‐center, and p‐facility cent‐dian problems are special cases. Other problems of this form include a large number of obnoxious facility problems, problems in which the objective is to minimize an Lk norm of distances, and a wide variety of problems, problems in which the objective is to minimize an Lk norm of distances, and a wide variety of problems in which equity or social welfare is a a factor.
Domination theory and the crapo β‐invariant
Authors: Huseby Arne Bang
Published: May 2007

Relations are established between the domination and minimum domination invariants and a matroid invariant known as the Crapo β‐invariant. Using these results, it is possible to extend well‐known results of domination theory. Moreover, the proofs of these results are considerably simplified. Matroid theory is made available to reliability applications by introducing a certain regularity assumption.
The minimum augmentation of any graph to a K‐edge‐connected graph
Authors: Cai Guo‐Ray , Sun Yu‐Geng
Published: May 2007

For a graph G0 = (V, E0) and an integer K, how many edges are needed for augmenting G0 to a K‐edge‐connected graph? Results in the literature have answered this in several special cases such as when G0 is a tree, or when K = 2. In this paper, we settle the problem in the general case where G0 can be any multigraph and K can be any positive integer. We obtained both good characterization and good algorithm for the problem. Applications of our algorithm are suggested in designing a reliable network aiming at the most effective use of exising network.
A composite algorithm for a concave‐cost network flow problem
Authors: Balakrishnan Anantharam , Graves Stephen C.
Published: May 2007

We consider the problem of routing multiple commodities between various origin—destination pairs in a network, at minimum total cost. Economies of scale in arc flow costs are modeled using piecewise linear, concave total‐cost functions for each arc. This model applies to a variety of medium‐ and long‐term planning contexts including transportation planning, design of communication networks, plant location and capacity expansion planning, production planning, and water resource management. We formulate the general problem as a mixed‐integer program and develop a composite algorithm to generate both good lower bounds and heuristic solutions. We also report on computational results for several randomly generated general networks (with up to 40 nodes, 359 arcs, and 60 commodities) and layered neetworks (with up to 60 nodes, 372 arcs, and 60 commodities). These tests demonstrate that even for relatively large problems, the composite algorithm is very effective in generating solutions with small gaps between the upper and lower bounds (1.7% on average for general networks, and 0.4% on average for layered networks); for 19 out of the 25 layered network problems, the method generated and verified the optimal solution.
The maximum independent set problem for cubic planar graphs
Authors: Burns James E.
Published: May 2007

A maximum independent set of a graph is a set of vertices with maximum cardinality such that no pair of vertices is connected by an edge. Choukhmane and Franco have presented a polynomial time approximation algorithm for the maximum independent set problem in cubic planar graphs. If M is taken as the ratio of the size of the independent set produced by their algorithm to the size of a maximum independent set of the input graph, then they show that their algorithm gives M ⩾ 6/7 for any cubic planar graph and M ⩾ 7/8 for a triangle‐free cubic planar graph. We give a new, stronger proof of thier result. The new proof shows that their algorithm actually gives M ⩾ 7/8 for all cubic planar graphs.
An algorithm for the resource constrained shortest path problem
Authors: Beasley J. E. , Christofides N.
Published: May 2007

In this paper we examine an integer programming formulation of the resource constrained shortest path problem. This is the problem of a traveller with a budget of various resources who has to reach a given destination as quickly as possible within the resource constraints imposed by his budget. A lagrangean relaxation of the integer programming formulation of the problem into a minimum cost network flow problem (which in certain circumstances reduces to an unconstrained shortest path problem) is developed which provides a lower bound for use in a tree search procedure. Problem reduction tests based on both the original problem and this lagrangean relaxation are given. Computational results are presented for the solution of problems involving up to 500 vertices, 5000 arcs, and 10 resources.
A continuous‐time network simplex algorithm
Authors: Anderson E. J. , Philpott A. B.
Published: May 2007

Given a network having costs and upper bound constraints on the flows in its arcs, the minimum‐cost network flow problem is that of finding flows which satisfy a flow‐conservation constraint at each node and minimize the total cost of the flow. If the arc capacities vary as functions of time, and storage is permitted at the nodes of the network, then the problem becomes an infinitedimensional linear program with a network structure. We describe an algorithm to solve such problems. This algorithm is a continuuous‐time version of the network simplex algorithm.
A new algorithm for general matching problems using network flow subproblems
Authors: Lessard Réjean , Rousseau Jean‐Marc , Minoux Michel
Published: May 2007

We describe a new algorithm for minimum cost perfect matching problems in arbitrary (nonbipartite) graphs based on an active constraint set strategy on the whole set of constraints defining the matching polytope (the so‐called Edmonds' constraints or blossom inequalities). At each step, the resulting subproblem reduces to a minium cost network flow problem which may be solved either via classical network flow algorithms, or via primal network flow algorithms. Finite convergence of the algorithm is proved under a nondegeneracy assumption and an anticycling procedure is defined for ensuring finite termination in degenerate cases. Computer experiments using a primal code for the network flow subproblems show that this approach appears to be competitive even with respect to the most efficient general matching codes currently described in the literature.
Edge‐vulnerability and mean distance
Authors: Favaron Odile , Kouider Mekkia , Mahéo Maryvonne
Published: May 2007

The mean distance of a simple connected graph G of order n is defined by magnified image We answer a problem of Plesnik about the edge‐vulnerability of G related to μ, i.e., we find a bound for μ(G − e) − μ(G) and for magnified image where e is an edge of G such that G − e is still conencted. This question is of interest in interconnection La distance moyenne d'un graphe G, simple et connexe, d'ordre n, est définie par magnified image Nous répondons ici à un problème de Plesnik sur l'arěte‐vulnérabilité de G par rapport à μ, i.e. nous trouvons une borne pour μ(G −e) − μ(G) et pour magnified image oú e est une arěte de G telle que G − e soit encore connexe.
Reduction tests for the steiner problem in grapsh
Authors: Duin C. W. , Volgenant A.
Published: May 2007

Before actually solving the Steiner problem in graphs, it is knwon that recution tests may reduce the problem size, e. g., by eliminating vertices from the graph. We improve existing tests and develop new techniques based on a bottleneck approach. The latter include optimal edge detection, edge elimination, and node elimination because of degree considerations. We give computational results of a recution algorithm on a large number of test problem. These problems have up to 200 vertices; their edge densities vary from sparse to complete with Euclidean weights as well as unifirmly random. The algorithm solves the majority of the test problems by recution tests only, and reduces the size of the remaining problems to at most one fourth of the original size.
The prize collecting traveling salesman problem
Authors: Balas Egon
Published: May 2007

The following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every city that he vitis and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and net penalties, while visiting enough cities to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem (PCTSP). This paper discusses structural properties of the PCTS polytope, the convex hull of solutions to the PCTSP. In particular, it identifies several families of facet defining inequalities for this polytope. Some of these inequalities are related to facets of the ordinary TS polytope, others to facets of the knapsack polytope. They can be used in algorithms for the PCTSP either as cutting planes or as ingredients of a Lagrangean optimand.
On the separation number of a graph
Authors: Miller Zevi , Pritikin Dan
Published: May 2007

We consider the following graph labeling problem, introduced by Leung et al. (J. Y‐T. Leung, O. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput. 13 (1984) 650–667). Let G be a graph of order n, and f a bijection from V(G) to the integers 1 through n. Let |f|, and define s(G), the separation number of G, to be the maximum of |f| among all such bijections f. We first derive some basic relations between s(G) and other graph parameters. Using a general strategy for analyzing separation number in bipartite graphs, we obtain exact values for certain classes of forests and asymptotically optimal lower bounds for grids and hypercubes.
A comparison of phase and nonphase network flow algorithms
Authors: Martel Charles
Published: May 2007

We compare the performance of network flow algorithms based on Dinic's layered graph approach to the new Goldberg‐Tarjan (GT) algorithm. We show that for networks with small capacities, in particular for unit networks, the Dinic‐like algorithms are asymptotically faster than the GT algorithm. A second setting that we study is parameterized flow computations. Gallo, Grigoriadis, and Tarjan have shown that the GT algorithm solves this type of problem very efficiently. We show that traditional implementations of the Dinic‐like algorithms are much less efficient for solving parameterized flow problems. We also give a new implementation of a Dinic‐like algorithm that is competitive with the GT algorithm on parameterized flow networks.
An algorithmic note on the gallai‐milgram theorem
Authors: Cameron Kathie
Published: May 2007

For any directed graph G with node‐set V(G), we present an O([V(G)]3) algorithm that finds a partition P of V(G) into directed paths and an independent set I of nodes, such that |P=|I| The existence of such a P and I is the Gallai‐Milgrm theorem. Where G is transitive and acyclic, the well‐known Dilworth theorem that min |P| = max |I| follows immediately. Where G is bipartitite and every edge of G is directed from node‐set U to node‐set V, P corresponds to a largest matching in G.
A combinatorial problem related to distributed loop networks
Authors: Du D.‐Z. , Hsu D. F. , Li Qiao , Xu Junming
Published: May 2007

The problem under consideration arises from studies on local networks and multimodule memory organizations. The ring network has been one of the popular network topologies used in the design and implementation of local area networks and other configurations. We consider here a generalization of the ring network by adding two fixed‐step links to each node. The resulting networks have low diameter, easy routing, and switching structure and therefore are suitable for implementation in the design of reliable networks. Let N denote the number of nodes in the network. For a given N, we are concerned with the problem of determining the best topologies to minimize the diameter (and, hence, the transmission delay) of the network. We obtain new classes of values of N for which topologies can be found that achieve the lower bound lb = [(√2N ‐ 1 ‐ 1)/2] for the minimum diameter. We also show that for some infinite classes of N this lower bound lb is not achievable.
Optimal location of a path or tree on a network with cycles
Authors: Richey Michael B.
Published: May 2007

This paper concerns the problem of locating a path‐ or tree‐shaped facility on a network. For median and center, min and max problems, we consider on which classes of networks the optimal facility location can be found in polynomial time. Some of these problems can be solved on series‐parallel graphs, but by high‐order polynomial‐ or pseudo‐polynomial‐time algorithms. Many of the problems that use pseudo‐polynomial time are shown to be NP‐complete on outerplanar graphs, a subset of series‐parallel graphs.
A graph‐theoretic approach to investigate structural and qualitative properties of systems: A survey
Authors: Yamada Takeo , Foulds Leslie R.
Published: May 2007

This article presents a survey of the current status of the research on structural and qualitative systems theory that has been conducted in the last few decades. This theory can be traced back to the work of Samuelson on comparative static analysis of a national economy. His problem was to find the direction of change in economic equilibrium induced by small changes in the exogenous variables of a system based solely on qualitative information such as the sign pattern of the parameters that specify the system. In the field of engineering, the work of Iri et al. on structural analysis of systems of equations and Lin's research on the structural controllability of dynamic systems were quite influential. Following these pioneering works, a variety of research has been carried out by mathematicians and engineers, as well as by economists. A few examples of problems are the structural solvability and decomposability of systems of equations, the structural characterization of Tinbergen's rule of economic policy, the structural controllability and decouplability of dynamic systems, and the sign‐solvability of static systems. Using graph‐theoretic terms with explanatory examples, this paper surveys the established results on the structural and qualitative analysis of systems in areas ranging from control theory to economics.
Independence properties of directed markov fields
Authors: Lauritzen S. L. , Dawid A. P. , Larsen B. N. , Leimer H.‐G.
Published: May 2007

We investigate directed Markov fields over finite graphs without positivity assumptions on the densities involved. A criterion for conditional independence of two groups of variables given a third is given and named as the directed, global Markov property. We give a simple proof of the fact that the directed, local Markov property and directed, global Markov property are equivalent and – in the case of absolute continuity w. r. t. a product measure – equivalent to the recursive factorization of densities. It is argued that our criterion is easy to use, it is sharper than that given by Kiiveri, Speed, and Carlin and equivalent to that of Pearl. It follows that our criterion cannot be sharpened.
Medical diagnosis using influence diagrams
Authors: De Bragança Pereira Carlos Alberto , Barlow Richard E.
Published: May 2007

Influence diagrams are used to illustrate how the probability of having a disease can be updated given the results from two or more clinical tests. The problem of calibrating a register using results from a survey, as discussed by Heldal and Spjøtvoll (1988), is solved using a Bayesian approach.
A lower bound for the steiner tree problem in directed graphs
Authors: Liu Weiguo
Published: May 2007

In this article, we introduce a new integer programming formulation for the minimum Steiner tree problem in directed graphs. With the observation that every Steiner tree contains a two‐terminal Steiner tree for every pair of the terminals, our formulation is based on the linear programming formulation for the two terminal Steiner tree polyhedron obtained by Ball et al. [2]. By the results of Ball et al. [2], this formulation contains a large class of facets that are different from those induced by the well‐known Steiner cut constraints. We give a general form of the dual ascent algorithm and discuss the relationship between this algorithm and the projection method for extended formulations. This dual ascent algorithm is applied to the new formulation to obtain a lower bound for the minimum Steiner tree problem. In the algorithm, we use the dual ascent algorithm introduced by Wong [16] as a subroutine and improve his lower bound. Some computational results are given in Section 3.
Worst‐case greedy matchings in the unit d‐cube
Authors: Snyder Timothy Law , Steele J. Michael
Published: May 2007

The worst‐case behavior of greedy matchings of n points in the unit d‐cube, where d ≥ 2, is analyzed. The weighting function is taken to be the α'th power of Euclidean distance, where 0 < α < d. It is proved that the asymptotic growth rate of the weight of such a greedy matching is exactly βn(d‐α)/d, where β is a positive constant that depends on the parameters α and d. Included in the analysis is a minimax theorem equating the worstcase behaviors of matchings resulting from greedy algorithms that, when ordering edges for the greedy process, break ties in different ways.
The search game on a network with immobile hider
Authors: Anderson E. J. , Aramendia M. A.
Published: May 2007

In this paper we discuss a search game on a network, Q, with two players, a searcher and a hider. The hider chooses a point on Q at which to hide, while the searcher starts at a given point on Q and moves with continuous trajectory subject to a maximal speed. This is a zero‐sum game with payoff given by the time elapsed until the searcher reaches the point occupied by the hider. The solution to this game is known for certain types of network. Here by formulating the problem as an infinite‐dimensional linear program, we derive an algorithm for its solution. We discuss the performance of the algorithm on three examples.
The network simplex method on a multiprocessor
Authors: Peters Jörg
Published: May 2007

We compare several implemented approaches to parallelizing the network simplex method on the SEQUENT shared memory multiprocessor. The experiments underscore the importance of parallel pricing and show that specialized processes and single pivots are more efficient than are uniform processes with parallel pivots. We describe the PARNET implementation that combines the best features of the experimental codes. In its least parallel version, PARNET outperforms NETFLO, a standard sequential code, by a factor of 12. The total execution time (including i/o and statistics) for any problem with 5000 nodes and 25,000 arcs taken from a standard set of NETGEN benchmark problems is less than 25 sec wall clock time on the Sequent Symmetry S‐81 using six processors. The incremental speedup is linear up to six processors on the test set and improves with the problem size and the density of the underlying graph. For a problem with 1000 nodes and 500,000 ares, PARNET achieves incremental linear speedup up to 12 processors.
A network equilibrium formulation of market disequilibrium and variational inequalities
Authors: Nagurney Anna , Zhao Lan
Published: May 2007

In this article, we consider an asymmetric market disequilibrium model in a spatial setting in the case of rigid prices and/or controls. In this problem, the markets need no longer clear. We show that the disequilibrium problem can be reformulated as an equilibrium problem over an abstract network with special structure. We then propose a network decomposition algorithm for the computation of the solution that exploits the structure and establishes convergence results using the theory of variational inequalities. Our computational results demonstrate the suitability of this approach for large‐scale market problems.
Maximum matchings in bipartite graphs via strong spanning trees
Authors: Balinski M. L. , Gonzalez J.
Published: May 2007

A new characterization of maximum matchings for bipartite graphs is presented. It is based on “strong spanning trees” and permits the development of a new algorithm that does not use the classical notion of augmenting paths and that runs in O(|V| |E|) time for bipartite graphs with |V| nodes and |E| edges.
Faster parametric shortest path and minimum‐balance algorithms
Authors: Young Neal E. , Tarjant Robert E. , Orlin James B.
Published: May 2007

We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum‐balance algorithm to obtain a faster minimum‐balance algorithm.

For a graph with n vertices and m edges, our parametric shortest path algorithm and our minimum‐balance algorithm both run in O(nm + n2 log n) time, improved from O(nm log n) for the parametric shortest path algorithm of Karp and Orlin and O(n2m) for the minimum‐balance algorithm of Schneider and Schneider.

An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is O(n log n + m).
The generalized folding‐cube network
Authors: Choi Sang Bang , Somani Arun K.
Published: May 2007

We present an enhanced hypercube architecture and develop a corresponding routing scheme to realize arbitrary permutations in this paper. In particular, we design a rearrangeable and reconfigurable static hypercube architecture called the Generalized Folding‐Cube in the circuit switching environment. In the proposed hypercube, we show that if each connection between two neighboring nodes consists of two pairs of links (two full‐duplex communication lines) the hypercube can handle two independent permutations simultaneously. This hypercube architecture can also be used as an efficient reconfigurable network.
Reliability covering problems
Authors: Ball M. O. , Provan J. S. , Shier D. R.
Published: May 2007

This paper studies the reliability covering problem, in which given routes provides service to various stops (e.g., of a transit system). If the routes are subject to failure, it is desired to find the probability that all stops will be covered by an operating route. It is shown that this problem is NP‐hard even when routes are defined with respect to an underlying tree. Polynomially solvable cases are developed when some additional structure is imposed on the routes of a tree: e.g., when the routes are directed paths of a rooted directed tree. These cases generalize reliability computations for consecutive k‐out‐of‐n systems as well as the extensions to consecutively connected systems studied by Shanthikumar and by Hwang and Yao.
Average properties of two‐dimensional partial orders
Authors: Sidney J. B. , Sidney S. J. , Warburton A.
Published: May 2007

The complexity of many combinatorial algorithms is directly related to the number of upsets (filters) in an underlying partial order or, equivalently, to the number of downsets (ideals) that are the complements of upsets. In this paper, we investigate the expected number of upsets in randomly generated two‐dimensional partial orders and present a number of new results, together with simple combinatorial proofs of some known results. As an application of our results, we show that some well‐known algorithms for precedence constrained scheduling have nonpolynomial expected time and storage complexity.
Efficient algorithms for generalized cut‐trees
Authors: Gusfield Dan , Naor Dalit
Published: May 2007

The Gomory–Hu cut tree is a compact and efficiently computed representation of selected minimum edge cuts in a weighted undirected graph G = (V, E) with n nodes. It represents () minimum cuts, one for each pair of nodes in G, and can be constructed with only n − 1 flow computations. In this article, we generalize the types of cut‐trees that can be efficiently constructed. We solve the open problem, posed by Hu [9], of constructing with n − 1 flows a cut‐tree for minimum node weighted cuts in an undirected graph. We then show how to build cut‐trees that compactly represent the minimum edge cuts in directed graphs, partially solving the open problem of constructing cut‐trees for weighted edge cuts in directed graphs.
An optimal algorithm to solve the all‐pair shortest path problem on interval graphs
Authors: Ravi R. , Marathe Madhav V. , Pandu Rangan C.
Published: May 2007

We present an O(n2) time‐optimal algorithm for solving the unweighted all‐pair shortest path problem on interval graphs, an important subclass of perfect graphs. An interesting structure called the neighborhood tree is studied and used in the algorithm. This tree is formed by identifying the successive neighborhoods of the vertex labeled last in the graph according to the IG‐ordering.
Location of facilities on a network subject to a single‐edge failure
Authors: Eiselt Horst A. , Gendreau Michel , Laporte Gilbert
Published: May 2007

In this work, the following location problem is analyzed. Let N = (V,E) be an undirected connected simple network, where V is the vertex set, |V| = n and E is the edge set. There is a nonnegative demand wj associated with every vertex uj. It is assumed that every edge (ui,uj) has a probability of failure pij and that failures can never occur on two edges simultaneously. The problem consists of locating p facilities on the network so that the total expected demand disconnected from the facilities is minimized. This problem occurs naturally in the fields of computer and telecommunications networks. A number of important results are proved. First, there always exists a solution in which all facilities are located at vertices. Second, the problem can always be solved optimally on the so‐called leaf‐tree associated with the network. Third, when p = 1, the problem is a 1‐median problem. When p > 1, there always exists an optimal solution for which all facilities are located at pendent vertices of the tree. Finally, when p > 2, the problem with p + 1 facilities can be solved in a greedy fashion, starting from a solution to the problem with p facilities. An exact algorithm for this problem is described. It can be executed in either O(np + |E|) time or in O(n log n + |E|) time. A numerical example is provided.
Degenerate Gilbert—Steiner trees
Authors: Weng J. F.
Published: May 2007

The minimal Gilbert network problem is a generalization of the Steiner minimal tree problem derived by adding flow‐dependent weights to the edges. The minimal Gilbert network is referred to as a minimal Gilbert—Steiner tree if it has a Steiner topology. All trees with Steiner topologies, obtained by sequentially contracting edges connecting given points and their incident Steiner points, form a degenerate tree family. Similarly to the Steiner problem, a relatively minimal tree satisfying some angle conditions is referred to as a Gilbert–Steiner tree. This work shows that, unlike the Steiner problem, there may exist more than one Gilbert–Steiner tree in a degenerate tree family. It is proved that the maximum number of Gilbert–Steiner trees in a degenerate tree family is 2[(n−2)/2]. A necessary condition for the minimal Gilbert–Steiner tree is also given.
Two algorithms for the subset interconnection design problem
Authors: Prisner Erich
Published: May 2007

An NP‐complete generalization of the minimum spanning tree problem is considered. Given are a set of V, a cost function c: V × V → R+, and a collection {X1, …, Xm} of subsets of V. A graph G with vertex set V is called feasible if every Xi induces a connected subgraph of G. The minimum subset interconnection design problem is to find a feasible graph with a minimum cost sum. In this paper, two heuristic algorithms for the problem are given and analyzed. Several classes of input data for which one of the algorithms finds optimal or at least approximative solutions are presented.
The swapping problem
Authors: Anily S. , Hassin R.
Published: May 2007

Each vertex of a graph initially may contain an object of a known type. A final state, specifying the type of object desired at each vertex, is also given. A single vehicle of unit capacity is available for shipping objects among the vertices. The swapping problem is to compute a shortest route such that a vehicle can accomplish the rearrangement of the objects while following this route. We exhibit several structural properties of shortest routes and develop polynomial approximation algorithms that are variations of a well‐known “patching” algorithm for the traveling salesman problem. We prove tight constant performance guarantees for these algorithms and note as a side product that these bounds hold and are tight also for the latter problem.
Reliabilities of chordal rings
Authors: Hu X. D. , Hwang F. K.
Published: May 2007

A chordal ring is a degree‐3 regular graph with n vertices on a ring and n/2 chords determined by a parameter h. Chordal rings are attractive as topologies for computer networks due to their simple structures and short diameters. In this work, we study the reliabilities of chordal rings assuming each edge can independently fail with probability p. For p small, the usual criterion to measure the reliability of a network is its line‐connectivity. We show that all chordal rings have the same line‐connectivity and the same super line‐connectivity. We analyze the reliabilities of chordal rings by using the recently developed notions of isolated and nonisolated cutsets and list the optimal choices of h for n ≤ 30.
An explicit construction of Euler circuits in shuffle nets and related networks
Authors: Etzion Tuvi , Bar‐David Israel
Published: May 2007

In this paper, we present a construction of Euler circuits for some circular multistage interconnection networks, which have a uniform structure between consecutive stages.
Degree‐five Steiner points cannot reduce network costs for planar sets
Authors: Rubinstein J. H. , Thomas D. A. , Weng J. F.
Published: May 2007

We show that a degree‐five Steiner point can never appear in a least‐cost planar network; that is we show that a degree‐five Steiner point actally increases the cost.
Scheduling file transfers in fully connected networks
Authors: Rivera‐Vega Pedro I. , Varadarajan Ravi , Navathe Shamkant B.
Published: May 2007

We consider the problem of transferring a set of files from their given locations in a fully connected network to their respective target locations in minimum time. We show that this problem is NP‐hard even with the restriction that no file uses more than two edges in its route. We present an efficient algorithm to solve this problem in the case when there is only one source and one or more destinations. For the general case, we propose a two‐phase approach to find two‐edge schedules that are optimal or close‐to‐optimal. In Phase I, two‐edge routes are assigned to files; in Phase II, a schedule is determined for the use of the links in these routes. For Phase I, we present an exact solution that is based on integer programming formulation and also give theoretical bounds for approximate solution. We also propose a route assignment algorithm that attempts to assign routes of minimum congestion. For Phase II, we present an efficient algorithm that constructs a schedule from the solution obtained in the first phase.
Finding disjoint paths with different path‐costs: Complexity and algorithms
Authors: Li Chung‐Lun , Thomas McCormick S. , Simchi‐Levi David
Published: May 2007

Consider a network G = (V,E) with distinguished vertices s and t, and with k different costs on every edge. We consider the problem of finding k disjoint paths from s to t such that the total cost of the paths is minimized, where the jth edge‐cost is associated with the jth path. The problem has several variants: The paths may be vertex‐disjoint or arc‐disjoint and the network may be directed or undirected. We show that all four versions of the problem are strongly NP‐complete even for k = 2. We describe polynomial time heuristics for the problem and a polynomial time algorithm for the acyclic directed case.
The Capacitated Arc Routing Problem: Lower bounds
Authors: Benavent E. , Campos V. , Corberan A. , Mota E.
Published: May 2007

In this paper, we consider the Capacitated Arc Routing Problem (CARP), in which a fleet of vehicles, based on a specified vertex (the depot) and with a known capacity Q, must service a subset of the edges of a graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. New lower bounds are developed for this problem, producing at least as good results as the already existing ones. Three of the proposed lower bounds are obtained from the resolution of a minimum cost perfect matching problem. The fourth one takes into account the vehicle capacity and is computed using a dynamic programming algorithm. Computational results, in which these bounds are compared on a set of test problems, are included.
Level graphs and approximate shortest path algorithms
Authors: Shapiro Jacob , Waxman Jerry , Nir Danny
Published: May 2007

Shortest path algorithms for graphs have been widely studied and are of great practical utility. For the case of a general graph, Dijkstra's algorithm is known to be optimal. However, in many practical instances, there is a “level” structure which may be imposed on the underlying graph. Utilizing these levels, this paper demonstrates that the time complexity of shortest path generation may be greatly reduced.

A new graph structure, the level graph, together with a simple uniformed heuristic, LGS, for searching that structure is introduced, which allows for rapid generation of approximate shortest paths. LGS is studied both analytically and via simulation. It is shown that the length of the path produced by LGS converges rapidly to that of the actual shortest path as the distance between the points increases.
Efficient parallel algorithms for bipartite permutation graphs
Authors: Chen Lin , Yesha Yaacov
Published: May 2007

In this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem; and others. All these problems can be solved inO(log2n) time withO(n3) processors on a Common CRCW PRAM. We also show that the minimum fill‐in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm. ©1993 by John Wiley & Sons, Inc.