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
0.8981572
0 references
0 references
0.8939953
0 references
0.88604254
0 references
0.88401914
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