Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

Finding the critical path in an activity network with time-switch constraints

An activity network is an acyclic graph with non-negative weights and with a unique source and destination. A project consisting of a set of activities and precedence relationships can be represented by an activity network and the mathematical analysis of the network provides useful information for managing the project. In a traditional activity network, it is assumed that an activity always begins after all of its preceding activities have been completed. This assumption may not be adequate enough to describe some practical applications where some forms of time constraints are attached to an activity. In this paper, we investigate one type of time constraint called time-switch constraint which assumes that an activity begins only in a specified time interval of a cycle with some pairs of exclusive components. Polynomial time algorithms are developed to find the critical path (or longest path) and analyze the float of each arc in this time-constrained activity network. The analysis shows that the critical path and float in this context differ from those of a traditional activity network in some management perspectives and thus, consideration of the time-switch constraint leads to enhanced project management through more effective use of budgets and resource allocation.     

The complexity of a minimum reload cost diameter problem

We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P=NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85].     

The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed digraph H, the homomorphism problem is to decide whether an input digraph D admits a homomorphism to H or not, and is denoted as HOM(H).An optimization version of the homomorphism problem was motivated by a real-world problem in defence logistics and was introduced in Gutin, Rafiey, Yeo and Tso (2006) [13]. If each vertex u∈V(D) is associated with costs c_i(u),i∈V(H), then the cost of the homomorphism f is ∑_u∈V(D)c_f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem forH and denote it as MinHOM(H). The problem is to decide, for an input graph D with costs c_i(u),u∈V(D),i∈V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost.Although a complete dichotomy classification of the complexity of MinHOM(H) for a digraph H remains an unsolved problem, complete dichotomy classifications for MinHOM(H) were proved when H is a semicomplete digraph Gutin, Rafiey and Yeo (2006) [10], and a semicomplete multipartite digraph Gutin, Rafiey and Yeo (2008) [12] and [11]. In these studies, it is assumed that the digraph H is loopless. In this paper, we present a full dichotomy classification for semicomplete digraphs with possible loops, which solves a problem in Gutin and Kim (2008) [9].     

A new algorithm for finding the shortest path between a specified pair of nodes in a graph of nonnegative arcs

This paper presents a new algorithm for finding the shortest path between a specified pair of nodes in a directed nonnegatively weighted graph. The average number of operations of this algorithm is competitive with that of the best existing algorithm presented by Dijkstra.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

Finding K shortest looping paths with waiting time in a time–window network

A time-constrained shortest path problem is a shortest path problem including time constraints that are commonly modeled by the form of time windows. Finding K shortest paths are suitable for the problem associated with constraints that are difficult to define or optimize simultaneously. Depending on the types of constraints, these K paths are generally classified into either simple paths or looping paths. In the presence of time–window constraints, waiting time occurs but is largely ignored. Given a network with such constraints, the contribution of this paper is to develop a polynomial time algorithm that finds the first K shortest looping paths including waiting time. The time complexity of the algorithm is O(rK²|V₁|³), where r is the number of different windows of a node and |V₁| is the number of nodes in the original network.     

A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.     

Limit theorems for the minimum interpoint distance between any pair of i.i.d. random points in R d

The limit theorem for the minimum interpoint distance between any pair of i.i.d. random points in R ^d with common density fL ² was studied by a method which makes use of the convergence of point processes. Some one-dimensional examples with fL ² (including the cases Beta and Gamma distributions) were also considered.     

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ_r(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then .     

Analysis of critical paths in a project network with fuzzy activity times

This paper proposes an approach to critical path analysis for a project network with activity times being fuzzy numbers, in that the membership function of the fuzzy total duration time is constructed. The basic idea is based on the extension principle and linear programming formulation. A pair of linear programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy total duration time at α. By enumerating different values of α, the membership function of the fuzzy total duration time is constructed, and the fuzzy critical paths are identified at the same time. Moreover, by applying the Yager ranking method, definitions of the most critical path and the relative degree of criticality of paths are developed; and these definitions are theoretically sound and easy to use in practice. Two examples with activity times being fuzzy numbers of L-R and L-L types discussed in previous studies are solved successfully to demonstrate the validity of the proposed approach. Since the total duration time is completely expressed by a membership function rather than by a crisp value, the fuzziness of activity times is conserved completely, and more information is provided for critical path analysis.