No label defined (Q4355707)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1064163
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1064163

      Statements

      5 May 1999
      0 references
      finite undirected graph
      0 references
      Martins' algorithm
      0 references
      spanning trees
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references