A Note on the Graph Augmentation Problem

Shuichi UENO; Katsufumi TSUJI; Yoji KAJITANI

Copy

Shuichi UENO, Katsufumi TSUJI, Yoji KAJITANI, "A Note on the Graph Augmentation Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E74-A, no. 4, pp. 679-680, April 1991, doi: .
Abstract: For a given 2-edge-connected graph G and a spanning tree T of G, the graph augmentation problem 2ECA (T,G) is to find a minimum edge set AE (G) such that T A is 2-edge-connected. This note proves that 2ECA (T, G) is solvable in polynomial time if G is series-parallel.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e74-a_4_679/_p

Copy

@ARTICLE{e74-a_4_679,
author={Shuichi UENO, Katsufumi TSUJI, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on the Graph Augmentation Problem},
year={1991},
volume={E74-A},
number={4},
pages={679-680},
abstract={For a given 2-edge-connected graph G and a spanning tree T of G, the graph augmentation problem 2ECA (T,G) is to find a minimum edge set AE (G) such that T A is 2-edge-connected. This note proves that 2ECA (T, G) is solvable in polynomial time if G is series-parallel.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - A Note on the Graph Augmentation Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 679
EP - 680
AU - Shuichi UENO
AU - Katsufumi TSUJI
AU - Yoji KAJITANI
PY - 1991
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E74-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1991
AB - For a given 2-edge-connected graph G and a spanning tree T of G, the graph augmentation problem 2ECA (T,G) is to find a minimum edge set AE (G) such that T A is 2-edge-connected. This note proves that 2ECA (T, G) is solvable in polynomial time if G is series-parallel.
ER -

IEICE TRANSACTIONS on Fundamentals