scientific article; zbMATH DE number 1064163

Let \(G(N, A)\) be a finite undirected graph, where \(N\) is the vertex set and \(A\subseteq \{(i,j): i,j\in N\}\setminus\{(i, i):i\in N\}\) is the edge set. We associate to each edge \((i,j)\) in \(A\) two positive integer weights, that is a cost \(c_{ij}\) and a capacity \(k_{ij}\). Let \(Y\) be a given set of subgraphs of \(G(N,A)\). For every subgraph \(T\) in \(Y\) we define: \[ c(T)= \sum_{(i,j)\in T} c_{ij}\quad\text{and} \quad k(T)= \min\{k_{ij}: (i,j)\in T\}, \] representing, the cost and the capacity of the subgraph \(T\), respectively. We consider the following general fractional problem: (P) Find a subgraph \(T'\) in \(Y\) minimizing the ratio \(c(T)/k(T)\) over the set \(Y\), namely: \(\min\{c(T)/\) \(k(T): T\in Y\}\). The particular case of problem (P), when \(Y\) is the set of paths between two given vertices of the graph \(G\) was studied by \textit{E. Q. V. Martins} [Discrete Appl. Math. 8, 189-194 (1984; Zbl 0572.90098)]. A generalization of Martins' algorithm was given by \textit{E. Tigan} [Econ. Comput. Econ. Cybern. Stud. Res. 24, No. 4, 53-59 (1989; Zbl 0719.90086)]. The purpose of this paper is to apply this general algorithm for a particular case of the set \(Y\). Namely, we take \(Y\) to be the set of all spanning trees of the graph \(G\). In this case, we solve problem (P) by the perturbation of its cost coefficients. We obtain an approximate optimal solution for the initial problem and we give an evaluation of the deviation from the optimal value.

Recommendations

Cited in

(1)

Finding a contour with the smallest mean expenses in a graph with variable arc lengths. The simplest case

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4355707)