TR-2009-10

Augmenting undirected node-connectivity by one

László Végh



Abstract

We present a min-max formula for the problem of augmenting the node-connectivity of a graph by one and give a polynomial time algorithm for finding an optimal solution. We also solve the minimum cost version for node-induced cost functions.
 

Previous version can be found here.


Bibtex entry:

@techreport{egres-09-10,
AUTHOR = {V{\'e}gh, L{\'a}szl{\'o}},
TITLE = {Augmenting undirected node-connectivity by one},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-10}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!