bluuebunny/crossref_metadata_2025 huggingface dataset:
Modulation of the amplitude of NAD(P)H fluorescence transients after synaptic stimulation
Authors: Brennan A.M. , Connor J.A. , Shuttleworth C.W.
Published: May 2007

In brain slices, excitatory synaptic stimulation results typically in transient initial decreases in NAD(P)H fluorescence, followed by longer‐lasting NAD(P)H increases that overshoot pre‐stimulus NAD(P)H levels before returning slowly to baseline. We concluded recently that mitochondrial metabolism (rather than NADH generation by glycolysis) was responsible for the “overshoot” phase of responses evoked in murine hippocampal slices. The present study examined factors that may influence the amplitude of the overshoot phase, without necessarily directly influencing mitochondrial or glycolytic metabolism. The amplitudes of overshoots were influenced strongly by changes in pre‐stimulus NAD(P)H fluorescence levels produced by a prior electrical stimulus. In contrast, these changes in pre‐stimulus redox state had little effect on the amplitude of evoked initial NAD(P)H decreases. Resting NAD(P)H fluorescence levels differed significantly across sub‐regions of each slice, however, this is not due to differences in resting redox state, and the relative amplitude of NAD(P)H overshoots were not different in different slice regions. Exposure to an A1 receptor agonist (CPA) reduced the amplitude of postsynaptic potentials, and preferentially reduced the amplitude of NAD(P)H overshoots, before initial oxidizing components of biphasic transients were reduced significantly. These results suggest that amplitudes of NAD(P)H overshoots may not be good quantitative measures of the intensity of a discrete stimulus, under some conditions where the stimulus is small relative to recent activity in the slice. Comparison of flavoprotein autofluorescence with NAD(P)H levels seems useful when making quantitative comparisons of responses from different regions of slices, where optical properties and ongoing activity may be substantially different. © 2007 Wiley‐Liss, Inc.
Neuroinflammation and regulation of glial glutamate uptake in neurological disorders
Authors: Tilleux Sébastien , Hermans Emmanuel
Published: May 2007

Oxidative stress, neuroinflammation, and excitotoxicity are frequently considered distinct but common hallmarks of several neurological disorders, including Parkinson's disease, amyotrophic lateral sclerosis, multiple sclerosis, and Alzheimer's disease. Although neuron degeneration and death are the ultimate consequences of these pathological processes, it is now widely accepted that alterations in the function of surrounding glial cells are key features in the progression of these diseases. In response to alteration in their local environment, microglia, commonly considered the resident immune cells of the nervous parenchyma, become activated and release a variety of soluble factors. Among these, proinflammatory cytokines and free radicals actively participate in the degenerative insults. In addition, excitotoxic neuronal damage resulting from excessive glutamate is frequently associated with impaired handling of extracellular glutamate by gliotic astrocytes. Although several research projects have focused on the biochemical mechanisms of the regulation of glial glutamate transporters, a relationship between activation of microglia and modulation of astrocytic glutamate uptake is now suggested. The aim of this review is to summarize and discuss the data showing an influence of inflammatory mediators and related free radicals on the expression and activity of glial glutamate transporters. © 2007 Wiley‐Liss, Inc.
Challenge, opportunity
Authors: Katz Harold A.
Published: May 2007

People named the losers in general failure to staff and equip legislature to make it coordinate branch.
Siege of a village
Authors: Hills Stuart L.
Published: May 2007

Rural areas find identity, institutions threatened by great influx of residents to new suburban towns.
To avoid collisions
Authors: Ford Henry
Published: May 2007

Ford calls for clear but fluid definitions of relations between government and business.
Inside 100 state parties
Authors: Childs Richard S.
Published: May 2007

League survey, bolstered by local scholars and researchers, reveals helter‐skelter situation.
Sharing of powers
Authors: Keith John P.
Published: May 2007

Existing home rule provisos are held incompatible with new patterns of federal‐state‐local relations.
Who is in control?
Authors: Kavanagh John C.
Published: May 2007

Better local organization, finance and coordination are keys to improving quality of community services.
Construction of efficient tree networks: The pipeline problem
Authors: Zadeh N.
Published: May 2007

It is observed that sample cost functions for the pipeline problem [1] are discretely convex, i.e., their graphs are discrete subsets of graphs of convex functions. As a result, it is shown that the pipeline problem may be attacked by using either a minimum cost flow approach, or a combination of dynamic programming and sorting. Problems with concave cost functions are shown to be relatively easy. Even for problems which are neither convex nor concave, it is shown that in certain instances, only a subset of the data for each cost function is relevant. Error bounds are presented when approximations to the original cost functions are used. Results obtained in [4] for a related problem are summarized.
On the existence of N‐connected graphs with prescribed degrees (n ≧ 2)
Authors: Wang D. L. , Kleitman D. J.
Published: May 2007

In this paper we provide a simple algorithm for constructing an n‐ (vertex) connected graph with no multiple edges or loops having degree sequence satisfying the conditions indicated below. We prove these to be necessary and sufficient for the existence of such a graph.

Our algorithm consists of constructing the graph in stages. An explicit construction is given if all degrees are n or n+1. Otherwise we choose a vertex with either the largest or smallest degree and connect it with a set of the remaining vertices having largest degrees, leaving a residual degree sequence for the rest of the graph which later can then be constructed by iteration. We connect the vertex of smallest degree above if the residual degrees after its connection are all at least n. Otherwise we connect the vertex of largest degree.

The conditions on the degree sequence are that it must be realizable by a graph, all degrees must be at least n, and the number of edges which can avoid touching the n‐1 largest degree vertices are sufficient to form a tree among the other vertices.
Cost allocation for a spanning tree
Authors: Claus A. , Kleitman D. J.
Published: May 2007

The problem of allocating cost in a spanning tree network is considered. A number of possible schemes are surveyed, and critically analyzed. Methods are suggested that are preferred given different emphases among the criteria for such a function.
On building minimum cost communication networks
Authors: Zadeh N.
Published: May 2007

The notion of an „exact”︁ test for improving network solutions is discussed. Computational results are presented which indicate the power of „exact”︁ tests relative to current marginal pricing schemes. It is conjectured that each cycle in an optimal solution must contain at least \documentclass{article}\pagestyle{empty}\begin{document}$ 1 + \frac{1}{{1^\alpha - 1}} $\end{document} links, where the cost of a link of length l and capacity y is proportional to 1·yα, 0 ≦ α ≦ 1.

A simple „exact”︁ test is presented for the one termianl TELPAK problem.
The chromatic reduction problem
Authors: Brown J. R.
Published: May 2007

The chromatic reduction problem is to find the minimum number of vertices that have to be eliminated from a graph so that the resultant subgraph has a chromatic number of k. When k = 1, the chromatic reduction problem reduces to finding the maximum internally stable set of a graph. An algorithm is developed for the chromatic reduction problem and computational experience is given.
A fundamental problem in vehicle routing
Authors: Orloff C. S.
Published: May 2007

An important but difficult combinatorial problem, in general, is to find the optimal route for a single vehicle on a given network. This paper defines a problem type, called the General Routing Problem, and gives an algorithm for its solution. The classical Traveling Salesman Problem and the Chinese Postman Problem are shown to be special limiting cases of the General Routing Problem. The algorithm provides a unified approach to both node and arc oriented routing problems, and exploits special properties of most real transportation networks such as sparsity of the associated adjacency matrix, and the tendency for arc symmetry at many nodes. For node oriented routing problems, this approach tends to produce large reduction in effective problem size.
Exact calculation of computer network reliability
Authors: Hänsler E. , McAuliffe G. K. , Wilkov R. S.
Published: May 2007

In designing a distributed computer network, the reliability and availability of the communication paths between all pairs of centers is a primary consideration. Many different approaches have been taken to calculate exactly the probability of successful communication between any specified pair of centers, for a given failure probability of the individual computer systems and communication facilities. However, almost all of these methods are not computationally feasible for large networks. Consequently, approximate calculations of network reliability have been suggested. In this paper a procedure is given for the exact calculation of the probability that all paths between a pair of nodes in a given network are interrupted. The procedure generates mutually exclusive sets of cutting states and calculates the probability of the related events. Summing these values one obtains the probability of service interruption between the specified pair of nodes. If all links fail with equal probability p, the coefficients of a polynomial can be calculated, describing the service disruption probability as a function of p.
Generalized Ramsey theory for graphs IV, the Ramsey multiplicity of a graph
Authors: Harary F. , Prins G.
Published: May 2007

A Proper graph G has no isolated points. Its Ramsey number r(G) is the minimum p such that every 2‐coloring of the edges of Kp contains a monochromatic G. The Ramsey multiplicity R(G) is the minimum number of monochromatic G in any 2‐coloring of Kr(G). With just one exception, namely K4, we determine R(G) for proper graphs with at most 4 points. For the stars K1,n, it is shown that R = 2n when n is odd and R = 1 when n is even. We conclude with the conjecture that for a proper graph, R(G) = 1 if and only if G = K2 or K1,n with n even.
A multicommodity flow problem
Authors: Kant E.
Published: May 2007

This paper presents an algorithm for finding maximal sized sets of flows in a certain class of multicommodity flow networks. The class consists of networks with integer capacity edges and with each node being a source or sink for all but at most one commodity. This new procedure lifts a restriction in a previous algorithm that required flow in edges joining source and sink of the same commodity.
Shortest alternating path algorithms
Authors: Brown J. R.
Published: May 2007

The concept of an alternating path has been very useful in analyzing matching problems and has formed the basis for a number of matching algorithms. However, no techniques have been devised to find the shortest alternating path in a weighted graph. This paper defines different types of directed and undirected alternating paths, and shows how the problem of finding the shortest directed alternating path can be transformed into a problem of finding the shortest path in a directed graph. Utilizing this transformation, an efficient algorithm is developed for finding the shortest undirected alternating path. Computational experience is given. Extensions of the techniques in this paper to other types of alternating paths are discussed.
A bit‐pushing shortest distance algorithm
Authors: Rosenthal A.
Published: May 2007

A bit manipulation method is given for finding shortest distances from an origin in an unweighted graph, or alternatively, for finding connected components. The basic approach is similar to some component algorithms already in the literature but an easy implementation is given that overcomes the problem which prevents the others from being efficient–namely, the problem of identifying the ones in a sparse bit string without checking all the bits. The algorithm would be most effective for moderate sized graphs (about 20–100 nodes). Computational results are given.
Optimal‐aim regulation and tracking in large‐order nonlinear networks
Authors: Barnard R. D.
Published: May 2007

A special regulation and tracking control strategy for large‐order nonlinear networks is introduced. A theorem useful for implementing this strategy and its application to several examples, including a well‐known transient power‐network model, are given.
Minimal complete matchings and negative cycles
Authors: Tobin R. L.
Published: May 2007

Conditions are developed which relate the existence of negative and nonpositive simple cycles in an undirected network to minimal complete matchings on a derived network. These conditions are then used to develop a test to determine whether or not an undirected network contains nonpositive simple cycles. Also, it is shown that, in certain cases, the solution to the matching problem gives information about the location of the nonpositive cycles.
Coding graphs by contractions
Authors: Geller D. P.
Published: May 2007

We propose a new parameter for studying the cohesiveness of graphs. The parameter is based on a technique for coding points by their images under various contractions. We find the value of this parameter for various classes of graphs, and investigate its behavior under three graphical products.
An algorithm for the longest cycle problem
Authors: Dixon E. T. , Goodman S. E.
Published: May 2007

An algorithm is presented which solves the problem of finding the longest simple cycle in an undirected edge‐weighted network. The properties of the vector spaces associated with the fundamental cycles of a network are used to develop a suitable algorithm for finding simple cycles, and this is imbedded into a branch and bound scheme that solves the longest cycle problem.
A new deterministic network reliability measure
Authors: Tainiter M.
Published: May 2007

We introduce and study properties of a new definition of connectivity and reliability which we call “mean connectivity.” The usual definition of cohesion which is used in survivability or reliability analysis is local in that it is the minimum size of an edge cutset. Mean connectivity involves an average time to connectivity, where the average is over random sequences of the edges of a graph. Aside from intuitive appeal, the new definition is shown to have desirable mathematical properties.
A generalized upper bounding approach to a communications network planning problem
Authors: McCallum C. J.
Published: May 2007

An important network optimization problem is to determine the routing of circuits and construction of additional are capacity in a communications network so as to satisfy forecasted circuit requirements at minimum cost. This paper considers the single‐time‐period version of the problem formulated as a linear program in the arc‐chain form. The special structure of this linear program is exploited to develop an efficient solution procedure. In particular, the generalized upper bounding technique devised by Dantzig and Van Slyke is applied. The computer implementation of the procedure is discussed and computational experience is reported. Brief mention is also made of certain extensions that are being pursued.
Measures of the restrictiveness of project networks
Authors: Thesen A.
Published: May 2007

The concept of the restrictiveness of project networks is defined to reflect the degree to which precedence requirements eliminate possible scheduling sequences. A suitable measure of restrictiveness is presented, as published related materials are shown not to apply. To extend the computational feasibility of the concept to larger networks, three indirect estimators of the measure are introduced. Relationships between these and related statistical properties of networks are shown. Finally, an algorithm to generate random networks with a specified restrictiveness is given.
Towards a theory of domination in graphs
Authors: Cockayne E. J. , Hedetniemi S. T.
Published: May 2007

This paper presents a quick review of results and applications concerning dominating sets in graphs. The domatic number of a graph is defined and studied. It is seen that the theory of domination resembles the well known theory of colorings of graphs.
A product form representation of the inverse of a multicommodity cycle matrix
Authors: Helgason R. V. , Kennington J. L.
Published: May 2007

When solving multicommodity network flow problems with either a primal or a dual partitioning technique one must carry and update a working basis inverse whose size need never exceed the number of saturated arcs (i.e. arcs for which there is no excess capacity). Efficient procedures have appeared in the literature for updating this inverse if it is carried in explicit form. However, for real world multicommodity network flow problems, this inverse may become quite large. In addition, this matrix may be quite dense even though the working basis may be sparse. In an attempt to obtain a sparse representation of this inverse matrix and simplify the computational burden, we present a new data structure along with the updating formulae for storing and updating this matrix. This data structure is a generalization of the well‐known product form procedure frequently used in mathematical programming codes.
Color‐feasible sequences of a multigraph
Authors: de Werra D.
Published: May 2007

Given a multigraph G, a sequence (h1,…, hm) of nonnegative integers h1 ≥… ≥ hm is color‐feasible for G if there is an edge‐coloring H1,…, Hm where Hi has exactly hi edges (i=1,…, m). It is known that the set C(G) of color‐feasible sequences of G is partially ordered. We show that if G is simple with maximum degree d, then all maximal sequences of C(G) have at most d+1 nonzero entries. This result can be extended to multigraphs. Furthermore, if the odd elementary cycles of a multigraph G satisfy some specified conditions then all maximal sequences have at most d+1 nonzero entries.
Optimal flows in nonlinear gain networks
Authors: Truemper K.
Published: May 2007

Computation of globally optimal flows in nonlinear gain networks is generally quite difficult. This paper identifies classes of these networks for which optimal solutions are easily obtained.
A mean‐time comparison of algorithms for the all‐pairs shortest‐path problem with arbitrary arc lengths
Authors: Kelton W. D. , Law A. M.
Published: May 2007

A mean‐time comparison of the algorithms of Floyd, Dantzig, Tabourier, and of repeated application of several single‐source algorithms, for the all‐pairs shortest‐path problem with arbitrary arc lengths clearly demonstrates the superiority of the Tabourier procedure for networks in which an average of at least 25% of the potential direct arcs are present. For very sparse networks, repeated application of a single‐source label‐correcting algorithm is found to be preferable.
On the numerical evaluation of some basic traffic formulae
Authors: Farmer R. F. , Kaufman I.
Published: May 2007

The problem of evaluating some basic traffic tormulae is considered here from a computational point of view. The specific problems include the evaluation of Poisson, Erlang B and Erlang C blocking functions and their associated inverses. Formulae related to Wilkinson's nonrandom traffic theory are also included. The methods presented are simple, efficient and accurate. They are based on several newly derived formulae and are ideally suited for extensive computerized network analysis, design and optimization problems. These methods have been incorporated into the simulator of the Canadian network. This simulator is widely used in analyzing the usage of the network as well as in assessing the impact of changing loads which arise from shifts in the economy, demand or rates.
Systematic searches for hypohamiltonian graphs
Authors: Collier J. B. , Schmeichel E. F.
Published: May 2007

A graph G is called hypohamiltonian if G is not hamiltonian but every vertex‐deleted subgraph G‐v is hamiltonian. The existence of a p‐vertex hypohamiltonian graph is open only for p = 14,17, and the existence of a p‐vertex, cubic hypohamiltonian graph is open only for p = 14,16,24,32. With the aid of a computer we have established that there is no hypohamiltonian graph of order 14, and no cubic hypohamiltonian graph of order 14 or 16. In addition, there is no hypohamiltonian graph of order 17 with girth ≥ 5. On the other hand, new p‐vertex, cubic hypohamiltonian graphs have been found for p = 18,22.
Permutation layout
Authors: Cutler M. , Shiloach Y.
Published: May 2007

The problems of layout of printed circuits and large scale integrated chips are very complex and are therefore usually approached by heuristic methods.

This paper presents a more analytic approach to an elementary subset of these problems, using combinatorial and graphtheoretic arguments.
Link designs and probability analyses for a class of connecting networks
Authors: Hwang F. K.
Published: May 2007

We study a class of five‐stage connecting networks which are generalizations of the AMDF networks recently proposed. The terminals of a network in this class are partitioned into various zones while two terminals of the same zone have a larger number of distinct paths connecting them than two terminals of different zones. Furthermore, to facilitate the analysis of blocking probabilities, we require that the linear graphs (union of all connecting paths) for all intrazone pairs of terminals be isomorphic and fixed, and the linear graphs for all interzone pairs be isomorphic.

We show that balanced incomplete block designs can be used to construct large classes of such networks. For a fixed number of distinct paths, we also determine the symmetric linear graph which has the smallest blocking probability, and show that the network which yields this linear graph (for interzone pairs) can always be constructed if a certain balanced incomplete block design exists.
Shortest paths with euclidean distances: An explanatory model
Authors: Golden B. L. , Ball M.
Published: May 2007

This paper considers the problem of finding the shortest path between an origin and destination pair in networks whose arc lengths are Euclidean distances. Dijkstra's algorithm and a modified version of Dijkstra's algorithm which is more adaptive to network topology are compared. We demonstrate on the infinite lattice network with diagonal arcs (a prototype of more general sparse Euclidean networks) that on the average the adaptive algorithm expands less than 8.3% the area that would be expanded by the Dijkstra algorithm and in the worst case it expands less than 10.7%. In addition, we present computational results for more general networks.
A new shortest path updating algorithm
Authors: Goto S. , Sangiovanni‐Vincentelli A.
Published: May 2007

A new algorithm for updating shortest paths from all vertices to a set of vertices following a decreasing‐length‐modification of some arcs, is presented. The algorithm is based on a formula which has an algebraic analogy with the well‐known Householder formula for inverting modified matrices. The number of operations (i.e., additions and comparisons) required for solving the modified shortest path problem is estimated as 0(mn2), where n is the overall number of vertices and m is a parameter related to the arcs which have been updated. The algorithm proposed here is particularly powerful for solving large‐scale networks with sparse structure.
The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
Authors: Chung F. R. K. , Hwang F. K.
Published: May 2007

Suppose P is a set of points in the plane with rectilinear distance. Let ls(P) denote the length of a Steiner minimal tree for P. Let lr(P) denote the semiperimeter of the smallest rectangle with vertical and horizontal lines which encloses P. It is well known that ls(P) ≥ lr(P) for ∣P∣ ≥ 3 where ∣P∣ denotes the cordinality of P.

In designing placement algorithms for printed circuits, lr(P) has been used as an estimate of ls(P) when ∣P∣ is small. Therefore, it is of some interest to know the value of

In this paper we show ρn tends to (√n+1)/2 and we give the exact value of ρn for n ≤ 10.
Exact and approximate algorithms for optimal network design
Authors: Dionne R. , Florian M.
Published: May 2007

ABSTRACT

In this paper, we present exact and approximate algorithms for the problem of optimal network design, which was first studied by Ridley [15], Stairs [17] and Scott [16], among others. Given a network, the problem consists in selecting a subset of links that minimizes the sum of shortest routes between all nodes subject to a budget constraint. Congestion effects are not considered. First, we refine a branch‐and‐bound algorithm proposed by Hoang [7] and we compare the resuling algorithm to an algorithm developed by Boyce et al. [1]. Our conclusion is that these exact algorithms perform adequately on medium size problems; however, for larger problems, approximate methods based on heuristic approaches are necessary. We then introduce two new heuristic approaches and test their computational efficiency as well as that of two other already known heuristics. The new heuristics presented produce excellent results. Finally, we consider more general versions of the problem.
Deferral strategies for a dynamic communications network
Authors: Smith R. L.
Published: May 2007

This paper deals with the problem of minimizing the present worth of expenditures for the expanding the capacity of a communications network in the face of an increasing demand for service. It is assumed that any economy of scale effects are dominated by savings due to expenditure deferral. A strategy is proposed that defers new construction of facilities by heuristic routing around exhausted facilities. Network solutions obtained by the deferral heuristic applied to a small prototype network compare favorably with exact solutions obtained by solving the underlying mixed integer LP.
A boolean theory of network flows and metrics and its applications to particle transmission and clustering
Authors: Onaga K. , Mayeda W.
Published: May 2007

A network N considered here is a graph (G,E) whose edge e is weighted by I(e) = [α(e), β(e)]. An admissible flow is a flow f satisfying α(e) ⊆ f (e) ⊆ β(e), for all e ⊂ E. A necessary and sufficient condition for existence of admissible Boolean flows in N, and characterization of maximum Boolean flows are presented. Then a property of maximum Boolean flows which are the terminal capacities of two‐terminal Boolean flows satisfy a Boolean triangular inequality is shown. Finally the concept of γ‐relativeness of a symmetric Boolean mapping m for any threshould γ⊆ S which induces a cluster decomposition of the node set V, by introducing Boolean network metrics is presented.
A cut‐flow procedure for transportation network optimization
Authors: Peterson Bruce E.
Published: May 2007

Many transportation network optimization problems use conservation of flow equations as constraints when a network must accommodate set flows between nodes. A different set of equations, called cut‐flow constraints, is developed to replace the conservation of flow equations. These constraints require that the flow over every separating cut be at least equal to total traffic requirements between nodes separated by the cut. In many network problems the cut‐flow constraints may prove more efficient than existing multicommodity formulations. The cut‐flow constraints are applied to the optimization problem of minimizing the sum of fixed and variable costs in a network.
Maximal expected flow in a network subject to arc failures
Authors: Aneja Y. P. , Nair K. P. K.
Published: May 2007

In a network subject to arc failures, each chain has a probability of failure. Therefore the maximal flow in the network is a random variable. The problem considered here is that of maximizing the expected flow. An arc‐chain formulation of the problem, and an algorithm for computing an optimal solution are provided. The algorithm involves a column generation technique, and a constrained chain in the network provides a desired column at each step of the simplex algorithm. The technique presented here is an extension of that of Ford and Fulkerson. The algorithm is validated, and a geometric interpretation is included.
Four‐terminus flows
Authors: Seymour P. D.
Published: May 2007

Suppose that s1, s2, s3, s4 are vertices of a graph, that each edge has a real‐valued capacity, and qii(1 ⩽ i < j ⩽ 4) are six demands. There exist flows from si to sj of value qij(1 ⩽ i < j ⩽ 4), such that the total flow through each edge does not exceed its capacity, if and only if the obvious connectivity requirements are satisfied. This result extends Hu's 2‐commodity flow theorem.
Complexity of network reliability computations
Authors: Ball Michael O.
Published: May 2007

This paper considers the difficulty of computing several measures of network reliability on directed and undirected networks. Results concerning the NP‐difficulty of several network reliability analysis problems are unified and in several cases generalized to wider classes of measures. Reductions are also given that relate network reliability problems on directed and undirected networks and problems with and without node failures.
An algorithm for the traffic assignment problem
Authors: Weintraub Andrés , González Jaime
Published: May 2007

An optimization algorithm for the traffic assignment problem is presented. It is based on determining, for the flow corresponding to each origin at a time, a set of disjoint circuits with the most negative total marginal cost, followed by a unidimensional optimization along these circuits. The proposed method was compared to other well known approaches on randomly generated networks. In most cases the proposed method proved to be highly efficient, particularly when appropriate tighter stopping rules were used. In this sense, it was seen that when stopping rules were based on insufficiently tight tolerances, substantial errors could appear in the equilibrium traffic assignment.
Optimal clustering structures for hierarchical topological design of large computer networks
Authors: Kleinrock Leonard , Kamoun Farouk
Published: May 2007

Large packet switching computer networks on the order of hundreds or thousands of nodes will soon emerge to handle the fast‐growing demands in data communication and resource sharing among various information processing systems around the world. The network topology design problem has long been recognized as extremely complex and very quickly becomes unmanageable as the size of the network increases. Existing heuristic design procedures are quite efficient for the design of small to moderate‐sized networks (25–75 nodes); however, they become very costly and even prohibitive when dealing with large networks. A design methodology based on the hierarchical clustering of the network nodes is presented in this paper in order to alleviate the computational cost involved in the design. More specifically, the emphasis is on the determination of a clustering structure which minimizes the computational cost of the design. Such a cost is assumed to have a polynomial growth with the number of nodes in the subnet to be designed. We present optimum results both for the number of clusters, number of superclusters, etc., and for the number of hierarchical levels. An expression for the average delay of a message in such a hierarchical network is also provided in terms of the average delays in the subnets composing the network. This decomposition leads to the design of smaller subnetworks for which we can utilize present design strategies.
On testing isomorphism of permutation graphs
Authors: Colbourn Charles J.
Published: May 2007

A polynomial time algorithm for testing isomorphism of permutation graphs (comparability graphs of 2‐dimensional partial orders) is described. It operates by performing two types of simplifying transformations on the graph; the contraction of duplicate vertices and the contraction of uniquely orientable induced subgraphs.
An O(n log n) heuristic for steiner minimal tree problems on the euclidean metric
Authors: Smith J. Macgregor , Lee D. T. , Liebman Judith S.
Published: May 2007

An O(n log n) heuristic for the Euclidean Steiner Minimal Tree (ESMT) problem is presented. The algorithm is based on a decomposition approach which first partitions the vertex set into triangles via the Delaunay triangulation, then “recomposes” the suboptimal Steiner Minimal Tree (SMT) according to the Voronoi diagram and Minimum Spanning Tree (MST) of the point set. The ESMT algorithm was implemented in FORTRAN‐IV and tested on a number of randomly generated point sets in the plane drawn from a uniform distribution. Comparison of the O(n log n) algorithm with an O(n4) algorithm clearly indicates that the O(n log n) algorithm is as good as the previous O(n4) algorithm in achieving reductions in the ratio SMT/MST of the given vertex set. This is somewhat surprising since the O(n4) algorithm considers more potential Steiner points and alternative tree configurations.
Sensitivity analysis of optimal matchings
Authors: Weber G. M.
Published: May 2007

After stating the weighted, perfect matching problem and briefly describing Edmonds' algorithm, certain postoptimality procedures are described. These procedures aid in reoptimizing related matching problems in which a few edge weights are altered. Regardless of the actual implementation of the matching algorithm used, when changing a single edge weight, the postoptimality procedures are on the order of cardinality (N) more efficient than solving the modified problem “from scratch,” where N is the node set of the underlying graph.
A generalized assignment heuristic for vehicle routing
Authors: Fisher Marshall L. , Jaikumar Ramchandran
Published: May 2007

We consider a common variant of the vehicle routing problem in which a vehicle fleet delivers products stored at a central depot to satisfy customer orders. Each vehicle has a fixed capacity, and each order uses a fixed portion of vehicle capacity. The routing decision involves determining which of the demands will be satisfied by each vehicle and what route each vehicle will follow in servicing its assigned demand in order to minimize total delivery cost. We present a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost. This heuristic has many attractive features. It has outperformed the best existing heuristics on a sample of standard test problems. It will always find a feasible solution if one exists, something no other existing heuristic can guarantee. It can be easily adapted to accommodate many additional problem complexities. By parametrically varying the number of vehicles in the fleet, our method can be used to optimally solve the problem of finding the minimum size fleet that can feasibly service the specified demand.
Exact solution of crew scheduling problems using the set partitioning model: Recent successful applications
Authors: Marsten Roy E. , Shepardson Fred
Published: May 2007

The set partitioning model of the crew rotation problem has been well known for many years. This paper focuses on recent developments that have made this model more attractive and have resulted in several successful implementations. These developments include improved problem conceptualizations and decompositions, as well as new solution techniques employing Lagrangian relaxation and subgradient optimization. Experience is reported from The Flying Tiger Line, Pacific Southwest Airways, Continental Airlines, and Helsinki City Transport. A case is made for work on heuristic decomposition methods to break large problems into moderate sized pieces that can be solved exactly.
Generalizations of Hoffman's existence theorem for circulations
Authors: Hassin Refael
Published: May 2007

Hoffman's Existence Theorem for circulations gives a necessary and sufficient condition for the existence of a feasible circulation in a directed network with upper and lower bounds on the flow along each of the arcs. This paper presents new existence theorems for more general types of flows in directed networks: flows with gains, two‐commodity flows, and flows with set constraints.
Finding maximum cliques in circle graphs
Authors: Rotem D. , Urrutia J.
Published: May 2007

A circle diagram consists of a circle C and a set of n chords. This diagram defines a graph with n vertices where each vertex corresponds to a chord, and two vertices are adjacent if their corresponding chords intersect in C. A graph G is called a circle graph if it is defined by some circle diagram. An algorithm which requires O(n2) steps to generate one maximum clique is presented. The algorithm can also be used to generate all maximum cliques where the number of steps need to generate each additional maximum clique is linear in its size. This compares favourably with Gavril's algorithm [4] which works in O(n3) steps.
A new concept of primeness in graphs
Authors: Lamprey R. H. , Barnes B. H.
Published: May 2007

A graph is quasiprime with respect to a boolean product of graphs if whenever it is a subgraph of the product of two graphs, it must necessarily be isomorphic to a subgraph of one of its factors. This paper provides a characterization of graphs quasi‐prime with respect to cartesian product, as well as graphs quasiprime with respect to other products.
Finding minimum rectilinear distance paths in the presence of barriers
Authors: Larson Richard C. , Li Victor O. K.
Published: May 2007

Given a set of origin‐destination points in the plane and a set of polygonal barriers to travel, this paper develops an efficient algorithm for finding minimal distance feasible paths between the points, assuming that all travel occurs according to the rectilinear distance metric. By geometrical arguments the problem is reduced to a finite network problem. The nodes are the origin‐destination points and the barrier vertices. The links designate those node pairs that “communicate” in a simple way, where communication implies the existence of a node‐to‐node rectilinear path that is not made longer by the barriers. The weight of each link is the rectilinear distance between its two corresponding nodes. Solution of the minimal distance path problem on the network procedes in two steps. First, for a given origin or root node, a tree is generated containing a minimal distance path to each node that communicates with the root node. Second, a modified Dijkstra‐type iteration is utilized, starting with the nodes of the tree, sequentially adding nodes according to minimum “penalty distance,” where the penalty is the extra travel distance caused by the barriers. The paper concludes with a discussion of the computational complexity of the procedure, followed by a numerical example.
Combinatorial properties of directed graphs useful in computing network reliability
Authors: Satyanarayana A. , Hagstrom Jane N.
Published: May 2007

This paper is concerned with the problem of computing the probability that a root vertex can communicate with all other vertices in a probabilistic directed graph. One method is to apply the inclusion‐exclusion principle of probability theory to the event “at least one rooted spanning tree of the graph is working.” We prove combinatorial properties of graphs which allow us to derive a much condensed form of the inclusion‐exclusion expression. Each term corresponds to an acyclic spanning subgraph of the original graph, with coefficient equal to (−1)b‐n+1, where b and n are the number of edges and vertices of the subgraph, respectively.
Mazes: Search games on unknown networks
Authors: Anderson E. J.
Published: May 2007

This paper discusses a class of search problems on networks, where the searcher only has information about that part of the network which he has traversed. These problems correspond to that of finding the exit of a maze. In this context it is natural to consider the two person game between the solver and the setter, where the setter may choose the maze subject to a constraint on the total length of its arcs. A particular strategy for the solver is investigated and shown to be optimal for this game.
A note on finding shortest path trees
Authors: Kershenbaum Aaron
Published: May 2007

Two shortest path algorithms are compared and it is shown that, while one outperforms the other in practice, the former's running time is exponential in the worst case while the latter's is polynomial. A procedure which constructs such worst case examples is given.
Some theoretical results in multiple path definition in networks
Authors: Moss Franklin H. , Merlin Philip M.
Published: May 2007

This paper is concerned with the problem of defining K multiple paths between pairs of nodes in a network. The treatment presented here is on a theoretical level, although the problem is motivated by a practical scheme for message routing in store‐and‐forward packet switched computer networks. Theorems are presented which offer readily testable sufficient conditions on the topology of a network which guarantee the existence of at least one set of paths under consideration. The proof of this theorem provides a generalized systematic method for constructing these paths if the sufficient conditions are met.
Minimum cost flow with set‐constraints
Authors: Hassin Refael
Published: May 2007

The minimum cost network flow problem with set‐constraints is a generalization of the well‐known minimum cost network flow problem, in which bounds on the sum of flows through sets of arcs exist. This paper investigates some variations of this problem, including the polymatroid intersection problem, where for each node two polymatroids are given; one polymatroid constrains flows entering the node, and the other constrains flows leaving it.
A decomposition algorithm for locating a shortest path between two nodes in a network
Authors: Jarvis John J. , Tufekci Suleyman
Published: May 2007

A decomposition algorithm for locating a shortest path between two nodes of a network with circuits (directed cycles) and arbitrary arc distances (with the customary assumption of no negative circuits) is introduced. Unlike similar decomposition algorithms by Hu [12, 13], Yen [23], and Glover, Klingman, and Napier [10], this algorithm finds only the shortest distance between two specified nodes. Computational complexity of this algorithm is shown to be better than the previous decomposition algorithms.
An algorithm for the equilibrium assignment problem with random link times
Authors: Sheffi Yosef , Powell Warren B.
Published: May 2007

In this article we offer an equivalent minimization formulation for the traffic assignment problem when the link travel times are flow‐dependent random variables. The paper shows the equivalency between the first‐order conditions of this program and the stochastic equilibrium conditions as well as the uniqueness of the solution. The paper also describes an algorithmic approach to the solution of this program, including a proof of convergence. Finally, we conduct some limited numerical experiments on the rate of convergence of the algorithm and the merits of the stochastic equilibrium model, in general, as compared with deterministic approaches.
On balance in group graphs
Authors: Harary Frank , Lindström Bernt , Zetterström Hans‐olov
Published: May 2007

We propose a generalization of signed graphs, called group graphs. These are graphs regarded as symmetric digraphs with a group element s(u, v) called the signing associated with each arc (u, v) such that s(u, v) s (v, u) = 1. A group graph is balanced if the product s(v1, v2) s (v2, v3) …s(um, v1) = 1 for each cycle v1, v2,…, vm, v1 in the graph. Let G denote the graph, F the group (not necessarily commutative), and s the signing. Then the group graph is denoted by (G, F, s). Given a group graph (G, F, s), which need not be balanced, we define the deletion index δ(G, F, s) as the minimum cardinality of a deletion set, which is a subset of lines whose deletion results in a balanced group graph. Similarly we define the alteration index γ(G, F, s) as the minimum cardinality of a alteration set, which is a set of lines {u, v} in the graph the values s(u, v) and s(v, u) of which can be changed so that the new group graph is balanced. When F is the group of order 2, we obtain a signed graph. Generalizing results known for signed graphs, we prove that minimal deletion sets are minimal change sets, which implies the equality δ(G, F, s) = γ(G, F, s) for all G, F, and s. We also prove the in‐equality δ (G, F, s) ≤ (n ‐ 1)q/n, where q is the number of lines in the graph G and n is the order of the group F. We conclude by studying δ for signed complete bigraphs Kn,n when the signing is determined from a Hadamard matrix.
The generalized diameter of a graph
Authors: Chen Chih‐Kang Eric , Garfinkel R. S.
Published: May 2007

We generalize the concept of the diameter of a graph G = (N, A) to allow for location of points not on the nodes. It is shown that there exists a finite set of candidate points which determine this generalized diameter. Given the matrix of shortest paths, an o (|A|2) algorithm is developed and tested.
Realizability of p‐point, q‐line graphs with prescribed point connectivity, line connectivity, or minimum degree
Authors: Boesch F. T. , Suffel C. L.
Published: May 2007

It is well known that certain graph‐theoretic extremal questions play a central role in the study of information network vulnerability. These extremal problems are special cases of the general question of realizability of graph invariants. For example a (p, Δ, δ, λ) graph is a graph having p‐points, maximum degree Δ, minimum degree δ, and line‐connectivity λ. An arbitrary quadruple of integers (a, b, c, d) is called (p, Δ, δ, γ) realizable if there is a (p, Δ, δ, γ) graph with p = a, Δ = b, δ = c, and γ = d. Necessary and sufficient conditions for a quadruple to be (p, Δ, δ, γ) realizable were recently given by the authors. In another manuscript they gave the solution to (p, Δ, δ, k) realizability, where k denotes the point connectivity. In this work we give necessary and sufficient conditions for (p, q, k), (p, q, γ), and (p, q, δ) realizability, where q denotes the number of lines of a graph.
A matroid related to finitely chainlike, countably infinite networks
Authors: Tucker A. C. , Zemanian A. H.
Published: May 2007

The determination of the currents and voltages in a countably infinite electrical network containing infinite energy requires not only the imposition of Kirchoff's laws and Ohm's laws but also the arbitrary assignment of the current‐voltage pairs in certain sets of branches, called joints. For finitely chainlike, countably infinite networks the maximal joint sets satisfy the base axioms of a matroid.
A property regarding degenerate pivots for linear assignment networks
Authors: Bazaraa Mokhtar S. , Sherali Hanif D.
Published: May 2007

Given an extreme point of an assignment polytope of size m, there exist 2m−1 mm−2 alternative basis representations according to the choice of the m ‐ 1 degenerate basic variables. This note establishes the basis structure which admits the maximum degenerate pivots and that which admits the minimum degenerate pivots. It is shown that the upper bound is achieved if and only if the basis is a chain graph and that the lower bound is achieved if the degenerate basic arcs all originate at some facility or all terminate at some location.