Augmenting undirected node-connectivity by one

(2011) Augmenting undirected node-connectivity by one. SIAM Journal on Discrete Mathematics, 25 (2). pp. 695-718. ISSN 0895-4801

Copy

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.

Item Type	Article
Keywords	node-connectivity,connectivity augmentation
Departments	Management
DOI	10.1137/100787507
Date Deposited	03 Oct 2012 09:06
URI	https://researchonline.lse.ac.uk/id/eprint/46408

Explore Further

Végh, László A.

QA Mathematics

http://www.lse.ac.uk/Mathematics/people/Laszlo-Vegh.aspx (Author)
10.1137/100787507 (DOI)

Full text not available from this repository.

Atom

BibTeX

OpenURL ContextObject in Span

OpenURL ContextObject

Dublin Core

MPEG-21 DIDL

Data Cite XML

EndNote

HTML Citation

METS

MODS

RIOXX2 XML

Reference Manager

Refer

ASCII Citation

Export

Downloads