http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7010
On the Hardness of Constructing Minimal Biconnected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality (Articolo in rivista)
- Type
- Label
- On the Hardness of Constructing Minimal Biconnected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality (Articolo in rivista) (literal)
- Anno
- 2002-01-01T00:00:00+01:00 (literal)
- Alternative label
Bockenhauer, H.J.; Bongartz, D.; Hromkovic, J.; Klasing, R.; Proietti, G.; Seiber, S.; Unger, W. (2002)
On the Hardness of Constructing Minimal Biconnected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality
in Lecture notes in computer science
(literal)
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Bockenhauer, H.J.; Bongartz, D.; Hromkovic, J.; Klasing, R.; Proietti, G.; Seiber, S.; Unger, W. (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Note
- ISI Web of Science (WOS) (literal)
- Titolo
- On the Hardness of Constructing Minimal Biconnected Spanning Subgraphs in Complete Graphs with Sharpened Triangle Inequality (literal)
- Abstract
- In this paper we investigate the problem of finding a 2-connected
spanning subgraph of minimal cost in a complete and weighted graph
$G$. This problem is known to be APX-hard, both for the edge- and
for the vertex-connectivity case. Here we prove that the
APX-hardness still holds even if one restricts the edge costs to an
interval $[1, 1+\epsilon]$, for an arbitrary small $\epsilon >
0$. This result implies the first explicit lower bound on the
approximability of the general problems.
On the other hand, if the input graph satisfies the sharpened
$\beta$-triangle inequality, then a $\left(\frac{2}+\frac{1}
\cdot \frac{\beta}{1-\beta}\right)$-approximation algorithm is
designed. This ratio tends to $ with $\beta$ tending to
$\frac{1}{2}$, and it improves the previous known bound of
$\frac{2}$, holding for graphs satisfying the triangle
inequality, as soon as $\beta < \frac{5}{7}$.
Furthermore, a generalized problem of increasing to 2 the
edge-connectivity of any spanning subgraph of $G$ by means of a
set of edges of minimum cost is considered. This problem is known to
admit a 2-approximation algorithm. Here we show that whenever
the input graph satisfies the sharpened $\beta$-triangle inequality
with $\beta < \frac{2}$, then this ratio can be improved to
$\frac{\beta}{1-\beta}$.
(literal)
- Prodotto di
- Autore CNR
Incoming links:
- Prodotto
- Autore CNR di
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
