http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7018
A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation (Articolo in rivista)
- Type
- Label
- A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation (Articolo in rivista) (literal)
- Anno
- 2002-01-01T00:00:00+01:00 (literal)
- Alternative label
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
- Galluccio, A.; Proietti, G. (literal)
- Pagina inizio
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- Rivista
- Note
- ISI Web of Science (WOS) (literal)
- Titolo
- A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation (literal)
- Abstract
- Given a weighted graph $G$ with $n$ vertices and $m$ edges, the
2-edge-connectivity augmentation problem is that of finding a
minimum weight set of edges of $G$ to be added to a spanning
subgraph $H$ of $G$ to make it 2-edge-connected. Such a problem is
well-known to be NP-hard, but it becomes solvable in polynomial time
if $H$ is a depth-first search tree of $G$, and the fastest
algorithm for this special case runs in $O(m+n \log n)$ time.
In this paper, we sensibly improve such a bound, by providing an
efficient algorithm running in $O(M \cdot \alpha(M,n))$ time,
where $\alpha$ is the classic inverse of the
Ackermann's function and $M=m \cdot \alpha(m,n)$. This algorithm has
two main consequences: First, it provides a faster $-approximation
algorithm for the general $-edge-connectivity augmentation
problem; second, it solves in $O(m \cdot \alpha(m,n))$ time
the problem of maintaining, by means of a minimum weight set of
edges, the $-edge-connectivity of a 2-edge-connected communication
network undergoing an edge failure, thus improving the previous
$O(m+n \log n)$ time bound.
(literal)
- Prodotto di
- Autore CNR
Incoming links:
- Prodotto
- Autore CNR di
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi