On the complexity of preflow-push algorithms for maximum-flow problems

We study the maximum-flow algorithm of Goldberg and Tarjan and show that the largest-label implementation runs inO(n ² m) time. We give a new proof of this fact. We compare our proof with the earlier work by Cheriyan and Maheswari who showed that the largest-label implementation of the preflow-push algorithm of Goldberg and Tarjan runs inO(n ² m) time when implemented with current edges. Our proof that the number of nonsaturating pushes isO(n ² m), does not rely on implementing pushes with current edges, therefore it is true for a much larger family of largest-label implementation of the preflow-push algorithms.Research performed while the author was a Ph.D. student at Cornell University and was partially supported by the Ministry of Education of the Republic of Turkey through the scholarship program 1416.     

On open shortest path first related network optimisation problems

The paper deals with flow allocation problems in IP networks using open shortest path first (OSPF) routing. Its main purpose is to discuss and propose methods for finding settlements of OSPF link weight system realising the assumed demand pattern for the given network resources (links capacities). Such settlements can result in a significantly better network performance, as compared with the simplified weight setting heuristics typically used nowadays. Although the configuration of the link weight system is primarily done in the network planning phase, still additional re-optimisations are feasible, and in fact essential, in order to cope with major changes in traffic conditions and with major resources’ failures and rearrangements.

The paper formulates a relevant OSPF routing optimisation problem, proves its NP-completeness, and discusses possible heuristic approaches and related optimisation methods for solving it. Two basic approaches are considered (the direct approach and the two-phase approach) and the resulting optimisation algorithms are presented. The considerations are illustrated with numerical results.     

Implicit branching and parameterized partial cover problems

Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well-known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems has been intensively studied in planar graphs and in graphs excluding a fixed graph H as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems.     

EIQNK curve analysis for the design of distribution center and warehouse with spline function

This paper discussed the EIQ and EIQNK curve metohd for the selection of machine and equipments in the design of distribution center or warehouse.This curve are expressed with orthogonal polynominals and spline functions and how the function applied of this problems.The shape of EIQNK curves are split into differents classes and discussed the characteristic of warehouse or distribution. Fuzzy EIQNK curve analysis also discussed.     

On a class of pursuit-evasion problems

This paper shows that a pursuit-evasion problem can be made amenable to solution with nonlinear programming algorithms by operating the pursuer and evader systems in a "discrete" mode of control and by choosing the cost function judiciously.     

A hierarchical solution approach for a multicommodity distribution problem under a special cost structure

Motivated by the spare parts distribution system of a major automotive manufacturer in Turkey, we consider a multicommodity distribution problem from a central depot to a number of geographically dispersed demand points. The distribution of the items is carried out by a set of identical vehicles. The demand of each demand point can be satisfied by several vehicles and a single vehicle is allowed to serve multiple demand points. For a given vehicle, the cost structure is dictated by the farthest demand point from the depot among all demand points served by that vehicle. The objective is to satisfy the demand of each demand point with the minimum total distribution cost. We present a novel integer linear programming formulation of the problem as a variant of the network design problem. The resulting optimization problem becomes computationally infeasible for real-life problems due to the large number of integer variables. In an attempt to circumvent this disadvantage of using the direct formulation especially for larger problems, we propose a Hierarchical Approach that is aimed at solving the problem in two stages using partial demand aggregation followed by a disaggregation scheme. We study the properties of the solution returned by the Hierarchical Approach. We perform computational studies on a data set adapted from a major automotive manufacturer in Turkey. Our results reveal that the Hierarchical Approach significantly outperforms the direct formulation approach in terms of both the running time and the quality of the resulting solution especially on large instances.     

The value of information in stochastic maximum flow problems

In this paper, we study the maximum flow problem in stochastic networks with random arc failures. We present the concept of expected value of a given flow and seek a flow whose expected value is maximum. We also introduce the concept of expected capacity of a given cut. While the expected capacity of a cut can be computed in polynomial time, we show that it is NP-hard to compute the expected value of a flow.     

GIS与电子商务下的物流管理

为更好地完善电子商务下的物流管理技术,讨论了GIS技术服务于物流管理的优势及其在物流分析中的应用,基于GIS的物流管理技术符合物流特点,能更好地满足电子商务下物流的发展。     

Waiting time distribution in a class of discrete-time cyclic service multi-queue systems

A new approximate method is developed for finding the waiting and sojourn time distributions in a class of multi-queue systems served in cyclic order at discrete intervals. An immediate application for such a model is in communication networks where a number of different traffic sources compete to access a group of transmission channels operating under a time-slotted sharing policy. This system maps naturally onto a model in which the inter-visit time has a probability mass function of phase-type. We derive a set of matrix equations with easily tractable iterative procedures for their solution and controllable accuracy in their numerical evaluation. We then validate the analytical model against simulation and discuss the validity of the assumptions. This methodology can be extended to several other polling strategies.     

Security concepts for the dynamics of autonomous vehicle networks

The secure operation of autonomous vehicle networks in the presence of adversarial observation is examined, in the context of a canonical double-integrator-network (DIN) model. Specifically, we study the ability of a sentient adversary to estimate the full network’s state, from noisy local measurements of vehicle motions. Algebraic, spectral, and graphical characterizations are provided, which indicate the critical role of the inter-vehicle communication topology and control scheme in achieving security.     

Finding non-dominated solutions in bi-objective integer network flow problems

This paper deals with an algorithm for finding all the non-dominated solutions and corresponding efficient solutions for bi-objective integer network flow problems. The algorithm solves a sequence of ?$?$-constraint problems and computes all the non-dominated solutions by decreasing order of one of the objective functions. The optimal integer solutions for the ?$?$-constraint problems are determined by exploring a branch-and-bound tree. The algorithm makes use of the network structure to perform the computations, i.e., the network structure of the problem is not destroyed with the inclusion of an ?$?$-constraint. This paper presents the main features of the algorithm, the theoretical bases of the proposed approach and some computational issues. Experiments were done and the results are also reported in the paper.     

Parametric analysis of overall min-cuts and applications in undirected networks

The overall min-cut problem in a capacitated undirected network is well known. Recently Stoer and Wagner gave an elegant algorithm for finding such a cut. In this paper we present a parametric analysis of such a cut where the capacity of an arc {i,j} in the network is given by min{b_ij,λ}, where λ is a parameter ranging from 0 to ∞. Letting function v(λ) denote the min-cut capacity, we develop an algorithm to describe v(λ) which involves at most n applications of Stoer and Wagner scheme, where n denotes the number of nodes in the network. We use v(λ) to determine an overall min-cut for multiroute flows as defined by Kishimoto. Such multi-route flows have interesting applications in communication networks.     

On the edge-tenacity of the middle graph of a graph

We consider the problem of efficiently breaking a graph into small components by removing edges. One measure of how easily this can be done is the edge-tenacity. Given a set of edges of G, the score of S is defined as sc(S)=[| S|+τ (G?S)]/[w(G?S)]. Formally, the edge-tenacity of a graph G is defined as T′(G)=min sc(S), where the minimum is taken over all edge-sets S of G. A subset S of E(G) is said to be a T′-set of G if T′(G)=sc(S). Note that if G is disconnected, the set S may be empty. For any graph G, τ(G?S) is the number of vertices in the largest component of G?S and w(G?S) is the number of components of G?S. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we give the edge-tenacity of the middle graph of specific families of graphs and its relationships with other parameters.     

On a class of optimization problems for framed structures

A unified treatment is presented for four types of problems on limit analysis of framed structures and related design problems. With the use of the lower bound theorem in plasticity these problems are formulated as standard linear programming problems. Two significant improvements are made. The new formulation of the design problems reduces the number of equations in the resulting linear program. An improved simplex algorithm for large and sparse linear programs is employed. The formulational and algorithmic improvements provide large capacity and high efficiency that are indispensable for computational analysis and design of large and complex structures.     

On the complexity of some colorful problems parameterized by treewidth

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.

1.

The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C_v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C_v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth.

2.

An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W[1]-hard for forests, parameterized by the number of colors on the lists.

3.

The list chromatic numberχ_l(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L_v of colors, where each list has length at least r, there is a choice of one color from each vertex list L_v yielding a proper coloring of G. We show that the problem of determining whether χ_l(G)?r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

     

On the efficiency of maximum-flow algorithms on networks with small integer capacities

The performance of maximum-flow algoirthms that work in phases is studied as a function of the maximum arc capacity,C, of the network and a quantity we call thetotal potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by Even and Tarjan, we derive a tightO(min{C ^1/3¦V¦^2/3,P ^1/2, ¦V¦}) upper bound on the number of phases. AnO(min{P log¦V¦,C¦V¦^3/2, ¦V¦²¦E¦}) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on ¦V¦ and ¦E¦ alone. We present an application of our bounds to the maximum subgraph density problem.     

On the schedulability of a data-centric real-time distribution middleware

This work presents an analysis of the Data Distribution Service for Real-Time Systems (DDS), a data-centric distribution middleware that supports the development of predictable applications, from the schedulability point of view. The study focuses on how DDS intends to guarantee the real-time behavior through the mechanisms included in the standard, and proposes some extensions to this standard. Furthermore, the paper looks at other approaches to build distributed systems based on object distribution and remote procedures calls which can guarantee predictability, and shows how to use DDS to obtain real-time applications. A set of concepts defined in the Modelling and Analysis of Real-Time and Embedded systems (MARTE) standard has been integrated into DDS in order to allow using Model-Driven Engineering (MDE) and schedulability analysis techniques. Finally, to emphasize the results obtained from the analysis, the paper also performs a brief evaluation to validate the predictability of a particular DDS implementation.     

On reliability indices of communication networks

The aim of this paper is to study the global reliability of communication networks. We assume that, in a communication network, the weights of the edges quantify the volume or the quality of the information transmitted by the nodes. In such a case, the strength of a path (resp. walk), called the reliability of the path (resp. walk) can be calculated as the product of the weights of the edges belonging to the paths (resp. walks). We introduce three indices to compute the reliability of a digraph (resp. graph). The first one is a version of Wiener index where we consider only the most reliable path between each pair of nodes. The second notion of reliability index considers reliability of all walks between each pair of nodes instead of taking into account only the most reliable path. The last one is a generalization of the functional centralization to the case of weighted networks. In this case, the notion of reliability index considers, for each node, the reliability of all closed walks starting and ending in the node. In addition, we propose a method for computing the introduced indices. Application of some of the proposed indices to trust-weighted social networks is also discussed.