The capacity scaling algorithm for the maximum flow problem runs in O(nmlogU) time where n is the number of nodes, m is the number of arcs, and U is the largest arc capacity in the network. The ...two-phase capacity scaling algorithm reduces this bound to O(nmlog(U/n)). This running time is achieved with the restriction that flows are pushed on individual arcs while paths are being identified, but this causes slower empirical run times compared to the single-phase capacity scaling algorithm. In this research, we prove that the two-phase algorithm runs in the same theoretical time without the mentioned restriction. We also show that in practice, it runs significantly faster than the single-phase capacity scaling algorithm.
The well-known problem of weighted matching in an arbitrary graph H with n vertices is reduced to a matching problem for a bipartite graph with 2n vertices. The maximum matching of graph H with the ...minimum sum of weights of edges defined by matrixc
ij
n
is found in timeO (
n
3
) after ordering, in non-descending order, the values above the main diagonal.
The paper considers the minimization of the sum of weights of edges forming a subset U′ ⊂ U of the set of disjoint simple cycles at vertices υ ϵ V in graph H = (V,U) and covering V. The problem under ...study (2-f problem) is polynomially solvable in algorithms that are characterized by technical difficulties that hinder the acceleration of computing. The 2-f problem is solved by reducing it to a simpler bipartite case. The result is represented by a perfect matching of bipartite graph corresponding to the solution of the assignment problem, where each circuit of cyclic expansion contains at least three arcs.
The paper proposes a new method to solve the assignment problem based on recursive derivation of the optimal solution. The assignment problem is formulated in the rearrangement matrix form that ...allows the use of the matrix approach to optimal solution. The algorithm is to find the minimum total weight matching in the bipartite graph with 2n vertices. The computational scheme of the recurrence method for solving the assignment problem is presented in the form adapted for implementation on a computer.
This paper first presents the method for finding a generalized augmenting path according to the idea of Dijkstra's algorithm. Then the combinatorial algorithm for solving the generalized maximum flow ...is given in lossy network. The algorithm runs in strongly polynomial times by finding the generalized f-augmenting path in a generalized residual network.
Intuitionistic fuzzy graphs of n-th Type (IFGsnT) model is a flexible model for evaluating human information. In order to establish the relation between some concepts of crisp graphs and fuzzy ...graphs, this paper aims to express the concept of matching in IFGsnTs.
This paper presents a new proof of a charaterization of fractional (g, f)-factors of a graph in which multiple edges are allowed. From the proof a polynomial algorithm for finding the fractional (g, ...f)-factor can be induced.
An algorithm for minimum-cost matching on a general graph with integral edge costs is presented. The algorithm runs in time close to the fastest known bound for maximum-cardinality matching. ...Specifically, n, m, and N denote the number of vertices, number of edges, and largest magnitude of cost, respectively. The best known time bound for maximum-cardinality matching is O(square root of n times m). A slight modification of the new algorithm finds a maximum-cardinality matching in that time bound. Other applications of the new algorithm are given, including an efficient implementation of Christofides' traveling salesman approximation algorithm and efficient solutions to update problems that require the linear programming duals for matching.
PDF
