A linear time algorithm for inverse obnoxious center location problems on networks

For an inverse obnoxious center location problem, the edge lengths of the underlying network have to be changed within given bounds at minimum total cost such that a predetermined point of the network becomes an obnoxious center location under the new edge lengths. The cost is proportional to the increase or decrease, resp., of the edge length. The total cost is defined as sum of all cost incurred by length changes. For solving this problem on a network with m edges an algorithm with running time ${\mathcal{O}(m)}$ is developed.     

Locally minimal uniformly oriented shortest networks

The Steiner problem in a λ-plane is the problem of constructing a minimum length network interconnecting a given set of nodes (called terminals), with the constraint that all line segments in the network have slopes chosen from λ uniform orientations in the plane. This network is referred to as a minimum λ-tree. The problem is a generalization of the classical Euclidean and rectilinear Steiner tree problems, with important applications to VLSI wiring design.A λ-tree is said to be locally minimal if its length cannot be reduced by small perturbations of its Steiner points. In this paper we prove that a λ-tree is locally minimal if and only if the length of each path in the tree cannot be reduced under a special parallel perturbation on paths known as a shift. This proves a conjecture on necessary and sufficient conditions for locally minimal λ-trees raised in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222]. For any path P in a λ-tree T, we then find a simple condition, based on the sum of all angles on one side of P, to determine whether a shift on P reduces, preserves, or increases the length of T. This result improves on our previous forbidden paths results in [M. Brazil, D.A. Thomas, J.F. Weng, Forbidden subpaths for Steiner minimum networks in uniform orientation metrics, Networks 39 (2002) 186-222].     

Polar Varieties,Real Equation Solving,and Data Structures: The Hypersurface Case

In this paper we apply for the first time a new method for multivariate equation solving which was developed for complex root determination to therealcase. Our main result concerns the problem of finding at least one representative point for each connected component of a real compact and smooth hypersurface. The basic algorithm yields a new method for symbolically solving zero-dimensional polynomial equation systems over the complex numbers. One feature of central importance of this algorithm is the use of a problem-adapted data type represented by the data structures arithmetic network and straight-line program (arithmetic circuit). The algorithm finds the complex solutions of any affine zero-dimensional equation system in nonuniform sequential time that ispolynomialin the length of the input (given in straight-line program representation) and an adequately definedgeometric degree of the equation system.Replacing the notion of geometric degree of the given polynomial equation system by a suitably definedreal (or complex) degreeof certain polar varieties associated to the input equation of the real hypersurface under consideration, we are able to find for each connected component of the hypersurface a representative point (this point will be given in a suitable encoding). The input equation is supposed to be given by a straight-line program and the (sequential time) complexity of the algorithm is polynomial in the input length and the degree of the polar varieties mentioned above.     

Toward optimal gossiping schemes with conference calls

n people have distinct bits of information which they can communicate by k-person conference calls. The object of gossip is to inform everyone of everyone else's information. Which networks admit a minimum call gossip scheme? For k = 2 a necessary and sufficient condition for such a network is that it is connected and contains a cycle of length 4. We address the same question for k>2. The values of n are partitioned into 2 classes: trivial and nontrivial. A necessary and sufficient condition is given for networks of size n for trivial n. For nontrivial n a sufficient condition is given and its necessity is conjectured.     

Scheduling independent jobs for torus connected networks with/without link contention

In this paper, we investigate the problem of how to schedule n independent jobs on an m × m torus based network. We develop a model to to quantify the effect of contention for communication links on the dilation of job execution time when multiple jobs share communication links; we then design an efficient algorithm to schedule a set of n independent jobs with different torus size requirements on a given torus with an objective to minimize the total schedule length. We also develop a feasibility algorithm for pre-emptively scheduling a given set of jobs on a torus of given size with a given deadline. We provide analysis for both the algorithms.     

The average path length of scale free networks

In this paper, the exact solution of average path length in Barabási–Albert model is given. The average path length is an important property of networks and attracts much attention in many areas. The Barabási–Albert model, also called scale free model, is a popular model used in modeling real systems. Hence it is valuable for us to examine the average path length of scale free model. There are two answers, regarding the exact solution for the average path length of scale free networks, already provided by Newman and Bollobas respectively. As Newman proposed, the average path length grows as log(n) with the network size n. However, Bollobas suggested that while it was true when m = 1, the answer changed to log(n)/log(log(n)) when m > 1. In this paper, as we propose, the exact solution of average path length of BA model should approach log(n)/log(log(n)) regardless the value of m. Finally, the simulation is presented to show the validity of our result.     

Analysis of an open tandem queueing network with population constraint and constant service times 1

We consider an open tandem queueing network with population constraint and constant service times. The total number of customers that may be present in the network can not exceed a given value K. Customers arriving at the queueing network when there are more than K customers are forced to wait in an external queue. The arrival process to the queueing network is assumed to be arbitrary. We show that this queueing network can be transformed into a simple network involving only two nodes. Using this simple network, we obtain an upper and lower bound on the mean waiting time. These bounds can be easily calculated. Validations against simulation data establish the tightness of these bounds.     

Representing edge intersection graphs of paths on degree 4 trees

Let P be a collection of nontrivial simple paths on a host tree T. The edge intersection graph of P, denoted by EPT(P), has vertex set that corresponds to the members of P, and two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in T. An undirected graph G is called an edge intersection graph of paths in a tree if G=EPT(P) for some P and T. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree network or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph.An undirected graph G is chordal if every cycle in G of length greater than 3 possesses a chord. Chordal graphs correspond to vertex intersection graphs of subtrees on a tree. An undirected graph G is weakly chordal if every cycle of length greater than 4 in G and in its complement possesses a chord. It is known that the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. Moreover, this provides an algorithm to reduce a given EPT representation of a weakly chordal EPT graph to an EPT representation on a degree 4 tree. Finally, we raise a number of intriguing open questions regarding related families of graphs.     

Gradient-Constrained Minimum Networks. III. Fixed Topology

The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value m, and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

Scheduling in a contaminated area: A model and polynomial algorithms

There are n jobs to be scheduled in a contaminated area. The jobs can be rescue, de-activation or cleaning works to be executed by a single worker in an area contaminated with radio-active or chemical materials. Precedence relations can be given on the set of jobs. An execution of each job can be preempted. However, the length of the minimal uninterrupted work period is given and it is the same for all jobs. Each work period for a job should be accompanied by a rest period whose length depends on the start time of the work period and its length. We focus on a short term planning problem. We show that this problem can be modelled by a scheduling problem with start time dependent job processing times. The dependency functions are exponentially decreasing ones. We also construct two polynomial time algorithms for the both cases—with and without precedence constraints.     

Matroids,generalized networks,and electric network synthesis

Matroid theory has been applied to solve problems in generalized assignment, operations research, control theory, network theory, flow theory, generalized flow theory or linear programming, coding theory, and telecommunication network design. The operations of matroid union, matroid partitioning, matroid intersection, and the theorem on the greedy algorithm, Rado's theorem, and Brualdi's symmetric version of Rado's theorem have been important for some of these applications. In this paper we consider the application of matroids to solve problems in network synthesis. Previously Bruno and Weinberg defined a generalized network, which is a network based on a matroid rather than a graph; for a generalized network the duality principle holds whereas it does not hold for a network based on a graph. We use the concept of the generalized network to formulate a solution to the following problem: What are the necessary and sufficient conditions for a singular matrix of real numbers, of order p and rank s, to be realizable as the open-circuit resistance matrix of a resistance p-port network. A simple algorithm is given for carriyng out the synthesis. We then present a number of unsolved problems, included among which is what could be called the four-color problem of network synthesis, namely, the resistance n-port problem.     

A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem

An O(n²) algorithm is presented for the n jobs m parallel machines problem with identical processing times. Due dates for each job are given and the objective is the minimization of the number of late jobs. Preemption is permitted. The problem can be formulated as a maximum flow network model. The optimality proof as well as other properties and a complete example are given.     

Knight's paths towards Catalan numbers

We provide enumerating results for partial knight's paths of a given size. We prove algebraically that zigzag knight's paths of a given size ending on the x-axis are enumerated by the generalized Catalan numbers, and we give a constructive bijection with peakless Motzkin paths of a given length. After enumerating partial knight's paths of a given length, we prove that zigzag knight's paths of a given length ending on the x-axis are counted by the Catalan numbers. Finally, we give a constructive bijection with Dyck paths of a given length.     

Calculation of minimal capacity vectors through k minimal paths under budget and time constraints

Reducing the transmission time is an important issue for a flow network to transmit a given amount of data from the source to the sink. The quickest path problem thus arises to find a single path with minimum transmission time. More specifically, the capacity of each arc is assumed to be deterministic. However, in many real-life networks such as computer networks and telecommunication networks, the capacity of each arc is stochastic due to failure, maintenance, etc. Hence, the minimum transmission time is not a fixed number. Such a network is named a stochastic-flow network. In order to reduce the transmission time, the network allows the data to be transmitted through k minimal paths simultaneously. Including the cost attribute, this paper evaluates the probability that d units of data can be transmitted under both time threshold T and budget B. Such a probability is called the system reliability. An efficient algorithm is proposed to generate all of lower boundary points for (d, T, B), the minimal capacity vectors satisfying the demand, time, and budget requirements. The system reliability can then be computed in terms of such points. Moreover, the optimal combination of k minimal paths with highest system reliability can be obtained.     

A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments

In this paper the following facility location problem in a mixed planar-network space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (A _i ,A _j ) is called covered if the time to access the network from A _i plus the time for traveling along the network plus the time for reaching A _j is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically.     

Combinatorics on partial word correlations

Partial words are strings over a finite alphabet that may contain a number of “do not know” symbols. In this paper, we consider the period and weak period sets of partial words of length n over a finite alphabet, and study the combinatorics of specific representations of them, called correlations, which are binary and ternary vectors of length n indicating the periods and weak periods. We characterize precisely which vectors represent the period and weak period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. We show that the sets of all such vectors of a given length form distributive lattices under suitably defined partial orderings. We show that there is a well-defined minimal set of generators for any binary correlation of length n and demonstrate that these generating sets are the primitive subsets of {1,2,…,n−1}. We also investigate the number of partial word correlations of length n. Finally, we compute the population size, that is, the number of partial words sharing a given correlation, and obtain recurrences to compute it. Our results generalize those of Guibas, Odlyzko, Rivals and Rahmann.     

Undesirable facility location with minimal covering objectives

An undesirable facility is to be located within some feasible region of any shape in the plane or on a planar network. Population is supposed to be concentrated at a finite number n of points. Two criteria are taken into account: a radius of influence to be maximised, indicating within which distance from the facility population disturbance is taken into consideration, and the total covered population, i.e. lying within the influence radius from the facility, which should be minimised. Low complexity polynomial algorithms are derived to determine all nondominated solutions, of which there are only O(n³) for a fixed feasible region or O(n²) when locating on a planar network. Once obtained, this information allows almost instant answers and a trade-off sensitivity analysis to questions such as minimising the population within a given radius (minimal covering problem) or finding the largest circle not covering more than a given total population.     

Complete Diagnostic Length 2 Tests for Logic Networks under Inverse Faults of Logic Gates

It is proved that any Boolean function can be implemented by a logic network in the basis {x&y &z, x ⊕ y, 1} in such a way that this logic network admits a complete diagnostic test of length at most 2 with respect to inverse faults at the outputs of logic gates.