Abstract This article presents a fast algorithm for a class of parametric assignment problems. Moreover, it is shown how this algorithm can be applied to a problem arising in the so‐called max‐algebra which results as an analogue of classical linear algebra by replacing the classical addition and multiplication by a ⊕ b = max(a,b) and a ⊗ b = a + b, respectively. An instance of the linear parametric assignment problem is given by a bipartite graph G = (U,V,E) with 2n vertices, m edges and affine‐linear parametric edge weights cλ(i,j) = c(i,j) − b(i,j)λ for (i,j) ∈ E. The task is to find an assignment with minimum weight with respect to the parametric weights cλ for all values of λ. We develop an algorithm which solves the special case for which b(i,j) ∈ {0, 1} for all (i,j) ∈ E in 𝒪(mn+n2 log n) time. Our algorithm can be extended to solve the special parametric assignment problem which arises in connection with computing the essential terms of the so‐called characteristic max‐polynomial. The resulting algorithm runs in 𝒪(n3) time and thus improves upon the best‐known algorithm for computing the characteristic max‐polynomial due to Burkard and Butkovič (Appl Math 130 (2003), 367–380) by a factor of n. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract A dynamic network consists of a directed graph with capacities, costs, and integral transit times on the arcs. In the minimum‐cost dynamic flow problem (MCDFP), the goal is to compute, for a given dynamic network with source s, sink t, and two integers v and T, a feasible dynamic flow from s to t of value v, obeying the time bound T, and having minimum total cost. MCDFP contains as subproblems the minimum‐cost maximum dynamic flow problem, where v is fixed to the maximum amount of flow that can be sent from s to t within time T and the minimum‐cost quickest flow problem, where is T is fixed to the minimum time needed for sending v units of flow from s to t. We first prove that both subproblems are NP‐hard even on two‐terminal series‐parallel graphs with unit capacities. As main result, we formulate a greedy algorithm for MCDFP and provide a full characterization via forbidden subgraphs of the class 𝒢 of graphs, for which this greedy algorithm always yields an optimum solution (for arbitrary choices of problem parameters). 𝒢 is a subclass of the class of two‐terminal series‐parallel graphs. We show that the greedy algorithm solves MCDFP restricted to graphs in 𝒢 in polynomial time. © 2004 Wiley Periodicals, Inc.

In the minimum-cost strong network orientation problem (MCSO), we are given an undirected graph G = (V, E) with nonnegative edge lengths 𝓁(e) and a transportation schedule T = {(s1, t1, w1), …, (sk, tk, wk)}, where wi units of weight have to be transported from the source vertex si to the target vertex ti for i = 1, …, k. Let Gσ be a strongly connected orientation of G and let L be the length of the shortest (directed) path from si to ti in Gσ. The goal in the MCSO is to find a strongly connected orientation Gσ such that the overall cost of the orientation given by Σ wiL (sum case) or maxi=1,…,k wiL (bottleneck case) is minimized. The strong network orientation problem is motivated by the practical problem of designing the optimal unidirectional flow path of automated guided vehicles. In this paper, we investigate the MCSO from the algorithmic and complexity points of view and propose a classification scheme. In the first part of the paper, we identify several efficiently solvable cases of the MCSO with sum and bottleneck objective functions which arise if additional restrictions are imposed on the structure of the graph G, the edge lengths 𝓁(e), and/or the transportation schedule T. In the second part, we identify special cases of the MCSO which are NP-hard. © 1999 John Wiley & Sons, Inc. Networks 33: 57–70, 1999

The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem with running time O(n2), where n is the number of vertices in the graph. Our result answers an open problem posed in a recent paper by Hochbaum and Pathria (1996). © 1999 John Wiley & Sons, Inc. Networks 33: 189–191, 1999