http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7065
Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems (Articolo in rivista)
- Type
- Label
- Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems (Articolo in rivista) (literal)
- Anno
- 2003-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
- Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems (literal)
- Abstract
- Given a 2-edge-connected, real 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. While the general
problem is NP-hard and $-approximable, in this paper we prove that
it becomes polynomial time solvable if $H$ is a depth-first search
tree of $G$. More precisely, we provide an efficient algorithm for
solving this special case which runs in ${\cal O}\big(M \cdot
\alpha(M,n)\big)$ 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 ${\cal O}(m \cdot \alpha(m,n))$ time the problem of
restoring, by means of a minimum weight set of replacement edges, the
$-edge-connectivity of a 2-edge-connected communication network
undergoing a link failure. (literal)
- Prodotto di
- Autore CNR
Incoming links:
- Prodotto
- Autore CNR di
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi