Finding extreme supported solutions of biobjective network flow problems: An enhanced parametric programming approach

We address the problem of determining a complete set of extreme supported efficient solutions of biobjective minimum cost flow (BMCF) problems. A novel method improving the classical parametric method for this biobjective problem is proposed. The algorithm runs in O(Nn(m + nlogn)) time determining all extreme supported non-dominated points in the outcome space and one extreme supported efficient solution associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported non-dominated points in outcome space for the BMCF problem. The memory space required by the algorithm is O(n + m) when the extreme supported efficient solutions are not required to be stored in RAM. Otherwise, the algorithm requires O(N + m) space. Extensive computational experiments comparing the performance of the proposed method and a standard parametric network simplex method are presented.     

Energy-efficient topology control algorithm for maximizing network lifetime in wireless sensor networks with mobile sink

Uneven energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large-scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. By using greedy policy and dynamic programming, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.     

Search space reduction in QoS routing

To provide real-time service or engineer constrained-based paths, networks require the underlying routing algorithm to be able to find low-cost paths that satisfy given quality-of-service constraints. However, the problem of constrained shortest (least-cost) path routing is known to be NP-hard, and some heuristics have been proposed to find a near-optimal solution. However, these heuristics either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. In this paper, we focus on solving the delay-constrained minimum-cost path problem, and present a fast algorithm to find a near-optimal solution. This algorithm, called delay-cost-constrained routing (DCCR), is a variant of the k-shortest-path algorithm. DCCR uses a new adaptive path weight function together with an additional constraint imposed on the path cost, to restrict the search space. Thus, DCCR can return a near-optimal solution in a very short time. Furthermore, we use a variant of the Lagrangian relaxation method proposed by Handler and Zang [Networks 10 (1980) 293] to further reduce the search space by using a tighter bound on path cost. This makes our algorithm more accurate and even faster. We call this improved algorithm search space reduction + DCCR (SSR + DCCR). Through extensive simulations, we confirm that SSR + DCCR performs very well compared to the optimal but very expensive solution.     

An efficient algorithm for the job-shop problem with two jobs

It is well known that job-shop scheduling problems with two jobs can be formulated as shortest path problems with obstacles in the plane. A reduction of this problem to an unrestricted shortest path problem in a special networkN is constructed inO (n logn) steps wheren is the number of obstacles. The shortest path inN can be found in timeO (n).     

A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n^2ε+n^1−ε) log n) time, performing O(n^1+ε log n) work for any 0<ε<1/2. The strength of the algorithm is its simplicity, making it easy to implement and presumable quite efficient in practice. The algorithm improves upon the work of all previous parallel algorithms. Our algorithm is based on a region decomposition of the input graph and uses a well-known parallel implementation of Dijkstra's algorithm. The logarithmic factor in both the work and the time can be eliminated by plugging in a less practical, sequential planar shortest path algorithm together with an improved parallel implementation of Dijkstra's algorithm.     

Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t∈V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n²logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n²logn).In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n²loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n²loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs.Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs.     

Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism

Data compression can be used to simultaneously reduce memory, communication and computation requirements of string comparison. In this paper we address the problem of computing the length of the longest common subsequence (LCS) between run-length-encoded (RLE) strings. We exploit RLE both to reduce the complexity of LCS computation from O(M×N) to O(mN+Mn−mn), where M and N are the lengths of the original strings and m and n the number of runs in their RLE representation, and to improve the inherent parallelism of the proposed algorithm, so that it may execute in O(m+n) steps on a systolic array of M+N units.We also discuss the application of the proposed algorithm to the related problem of edit distance (ED) computation.     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.     

Hybrid real-coded genetic algorithm for data partitioning in multi-round load distribution and scheduling in heterogeneous systems

Data partitioning and scheduling is one the important issues in minimizing the processing time for parallel and distributed computing system. We consider a single-level tree architecture of the system and the case of affine communication model, for a general m processor system with n rounds of load distribution. For this case, there exists an optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. This is a difficult optimization problem because for a given activation order, we have to first identify the processors that are participating (in the computation process) in every round of load distribution and then obtain the load fractions assigned to them, and the processing time. Hence, in this paper, we propose a real-coded genetic algorithm (RCGA) to solve the optimal activation order, optimal number of processors m* (m * ≤ m), and optimal rounds of load distribution n* (n * ≤ n), such that the processing time of the entire processing load is a minimum. RCGA employs a modified crossover and mutation operators such that the operators always produce a valid solution. Also, we propose different population initialization schemes to improve the convergence. Finally, we present a comparative study with simple real-coded genetic algorithm and particle swarm optimization to highlight the advantage of the proposed algorithm. The results clearly indicate the effectiveness of the proposed real-coded genetic algorithm.     

On the K best integer network flows

We address the problem of finding the K best integer solutions of a linear integer network flow problem. We design an O(f(n,m,L,U)+KmS(n,m,L)) time and O(K+m) memory space algorithm to determine the K best integer solutions, in a directed network with n nodes, m arcs, maximum absolute value cost L, and an upper bound U on arc capacities and node supplies. f(n,m,L,U) is the best time needed to solve the minimum cost flow problem in a directed network and S(n,m,L) is the best time to solve the single-source shortest path problem in a network with non-negative lengths. The introduced algorithm efficiently determines a “proper minimal cycle” by taking advantage of the relationship between the best solutions. This way, we improve the theoretical as well as practical memory space bounds of the well-known method due to Hamacher. Our computational experiments confirm this result.     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

Transition-aware DVS algorithm for real-time systems using tree structure analysis

Dynamic voltage scaling (DVS) is a key technique for embedded real-time systems to reduce energy consumption by lowering the supply voltage and operating frequency. Many existing DVS algorithms have to generate the canonical schedules or estimate the lengths of slack time in advance for generating the voltage scaling decisions. Therefore, these methods have to compute the schedules with exponential time complexities in general. In this paper, we consider a set of jitter-controlled, independent, periodic, hard real-time tasks scheduled according to preemptive pinwheel model. Our approach constructs a tree structure corresponding to a schedule and maintains the data structure at each early-completion point. Our approach consists of off-line and on-line algorithms which consider the effects of transition time and energy. The off-line and on-line algorithm takes O(k + n log n) and O(k + (p_max/p_min)) time complexity, respectively, where n, k, p_max and p_min denotes the number of tasks, jobs, longest and shortest task period, respectively. Experimental results show that the proposed approach is effective in reducing computational complexity, transition time and energy overhead.     

Semi-dynamic breadth-first search in digraphs

In this paper we propose dynamic algorithms for maintaining a breadth-first search tree from a given source vertex of a directed graph G in either an incremental or a decremental setting. During a sequence of q edge insertions or a sequence of q edge deletions the total time required is O(m·min{q,n}), where n is the number of vertices of G, and m is the final number of edges of G in the case of insertions or the initial number of edges of G in the case of deletions. This gives O(n) amortized time for each operation if the sequence has length Ω(m). Our algorithms require O(n+m) space. These are the first results in the literature concerning the dynamic maintenance of a breadth-first search tree for directed graphs. As a straightforward application of such algorithms we can maintain a shortest path tree for a directed graph in the case of unit edge weights within the same time bounds. In this case distance queries can be answered in constant time, while shortest path queries can be answered in time linear in the length of the retrieved path.     

An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5^n+o(n). This is the first algorithm breaking the trivial n!-barrier.     

Edit distance for a run-length-encoded string and an uncompressed string

We propose a new algorithm for computing the edit distance of an uncompressed string against a run-length-encoded string. For an uncompressed string of length n and a compressed string with M runs, the algorithm computes their edit distance in time O(Mn). This result directly implies an O(min{mN,Mn}) time algorithm for strings of lengths m and n with M and N runs, respectively. It improves the previous best known time bound O(mN+Mn).     

Petri net based decision system modeling in real-time scheduling and control of flexible automotive manufacturing systems

This paper presents the design and the implementation of a Petri net (PN) model for the control of a flexible manufacturing system (FMS). A flexible automotive manufacturing system used in this environment enables quick cell configuration, and the efficient operation of cells. In this paper, we attempt to propose a flexible automotive manufacturing approach for modeling and analysis of shop floor scheduling problem of FMSs using high-level PNs. Since PNs have emerged as the principal performance modeling tools for FMS, this paper provides an object-oriented Petri nets (OOPNs) approach to performance modeling and to implement efficient production control. In this study, we modeled the system as a timed marked graph (TMG), a well-known subclass of PNs, and we showed that the problem of performance evaluation can be reduced to a simple linear programming (LP) problem with m − n + 1 variables and n constraints, where m and n represent the number of places and transitions in the marked graph, respectively. The presented PN based method is illustrated by modeling a real-time scheduling and control for flexible automotive manufacturing system (FAMS) in Valeo Turkey.     

An optimization algorithm for free-form surface partitioning based on weighted gaussian image

Partitioning free-form surfaces into sub-patches and finding optimal representative normal for each patch to maximize a global objective function is an important two-level operation in diverse industrial applications. In this paper, by solving a maximum hemispherical partitioning problem raised from a weighted Gaussian image, an optimization algorithm is proposed to partition a free-form surface into two sub-patches and simultaneously report the optimal representative normals. By discretizing the free-form surface with W sample points and clustering normals on the surface with m distinct sample normals, the proposed algorithm is designed, in general, with O(m²W²) time complexity and O(W²) space complexity, and in particular, if the surface is convex, in O(m² log m) time complexity. Case studies with four representative examples are presented and a real world application is exploited to demonstrate the effectiveness and usefulness of the proposed algorithm.     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.