Title :
3-connectivity augmentation problems
Author :
Watanabe, Toshimasa ; Nakamura, Akira
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
Abstract :
The authors characterize a smallest 3-connectivity augmentation, involving the determination of a minimum set of edges to be added so as to 3-connect a given undirected simple graph. It is shown that there is an O( mod V mod ( mod V mod + mod E mod )/sup 2/) algorithm for finding a solution to the problem.<>
Keywords :
graph theory; minimisation; algorithm; minimum set of edges; smallest 3-connectivity augmentation; undirected simple graph; Electrocardiography; Particle separators; Terminology;
Conference_Titel :
Circuits and Systems, 1988., IEEE International Symposium on
Conference_Location :
Espoo, Finland
DOI :
10.1109/ISCAS.1988.15296